Given an array of positive integers target and an array initial of same size with all zeros.
Return the minimum number of operations to form a target array from initial if you are allowed to do the following operation:

Choose any subarray from initial and increment each value by one.

The answer is guaranteed to fit within the range of a 32-bit signed integer.
 
Example 1:
Input: target = [1,2,3,2,1]
Output: 3
Explanation: We need at least 3 operations to form the target array from the initial array.
[0,0,0,0,0] increment 1 from index 0 to 4 (inclusive).
[1,1,1,1,1] increment 1 from index 1 to 3 (inclusive).
[1,2,2,2,1] increment 1 at index 2.
[1,2,3,2,1] target array is formed.

Example 2:
Input: target = [3,1,1,2]
Output: 4
Explanation: (initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target).

Example 3:
Input: target = [3,1,5,4,2]
Output: 7
Explanation: (initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target).

Example 4:
Input: target = [1,1,1,1]
Output: 1

 
Constraints:

1 <= target.length <= 10^5
1 <= target[i] <= 10^5

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Greedy algorithms

Starter code: class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        

Solutions:
class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		prev = -1
		ans = 0
		for num in target:
			if prev == -1:
				prev = num
				ans += num
				continue
			if num > prev:
				ans += num - prev
			prev = num
		return ans


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		tLen = len(target)
		steps = target[0]
		reusableOperations = target[0]
		for i in range(1, tLen):
			if target[i] <= reusableOperations:
				reusableOperations = target[i]
			else:
				steps += target[i] - reusableOperations
				reusableOperations = target[i]
		return steps


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		ans = target[0]
		for i in range(1, len(target)):
			if target[i - 1] < target[i]:
				ans += target[i] - target[i - 1]
		return ans


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		ans = prev = 0
		for i in target:
			ans += max(0, i - prev)
			prev = i
		return ans


class Solution:

	def minNumberOperations(self, A: List[int]) -> int:
		res = pre = 0
		for a in A:
			res += max(0, a - pre)
			pre = a
		return res


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		diff = [0] * len(target)
		diff[0] = target[0]
		for (i, num) in enumerate(target[1:], 1):
			diff[i] = target[i] - target[i - 1]
		opr = 0
		for d in diff:
			if d > 0:
				opr += d
		return opr


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		ans = 0
		for i in range(1, len(target)):
			(pre, curr) = (target[i - 1], target[i])
			ans += max(curr - pre, 0)
		return ans + target[0]


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		ans = 1
		target = target + [1]
		pre = 1
		_max = 1
		_min = 10 ** 9
		for i in range(len(target) - 1):
			cur = target[i]
			if cur == 1:
				continue
			nex = target[i + 1]
			if cur <= nex:
				if nex > _max:
					_max = nex
			else:
				if nex < _min:
					_min = nex
				if cur > _max:
					_max = cur
				ans += min(_max - pre, _max - 1)
				pre = _min
				_min = 10 ** 9
				_max = nex
		return ans


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		res = 0
		for i in range(len(target)):
			if i == 0:
				res = target[0]
				continue
			d = target[i] - target[i - 1]
			if d > 0:
				res += d
		return res


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		return target[0] + sum([max(0, curr - pre) for (pre, curr) in zip(target, target[1:])])


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		return sum([max(b - a, 0) for (a, b) in zip([0] + target, target)])


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		stack = [0]
		res = 0
		for num in target:
			if num > stack[-1]:
				res += num - stack[-1]
			elif num < stack[-1]:
				while stack[-1] > num:
					stack.pop()
			stack.append(num)
		return res


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		tot = 0
		l = 0
		for t in target:
			if t > l:
				tot += t - l
				l = t
			elif t < l:
				l = t
		return tot


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		(prev, ans) = (None, 0)
		for t in target:
			if prev is not None:
				if t >= prev:
					ans += t - prev
			else:
				ans += t
			prev = t
		return ans


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		tLen = len(target)
		maxValInd = [target[0], 0]
		minValInd = [target[0], 0]
		steps = target[0]
		for i in range(1, tLen):
			if target[i] >= maxValInd[0]:
				if not maxValInd[1] <= minValInd[1] <= i - 1:
					steps += target[i] - maxValInd[0]
					maxValInd = [target[i], i]
					if target[i] <= minValInd[0]:
						minValInd = [target[i], i]
				else:
					steps += target[i] - minValInd[0]
					maxValInd = [target[i], i]
					minValInd = [target[i], i]
			else:
				maxValInd = [target[i], i]
				if target[i] <= minValInd[0]:
					minValInd = [target[i], i]
		return steps


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		num_increments = 0
		prev = 0
		for t in target:
			if t > prev:
				num_increments += t - prev
			prev = t
		return num_increments


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		result = 0
		for (index, value) in enumerate(target):
			if index == 0:
				result = value
			elif value > target[index - 1]:
				result += value - target[index - 1]
			pass
		return result


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		ans = target[0]
		d = 0
		base = target[0]
		for i in range(1, len(target)):
			if target[i] == target[i - 1]:
				continue
			elif target[i] < target[i - 1]:
				if d == 0:
					d = -1
				if d == 1:
					d = -1
					ans += target[i - 1] - base
			elif target[i] > target[i - 1]:
				if d == 0:
					d = 1
				if d == -1:
					d = 1
					base = target[i - 1]
		if d == 1:
			ans += target[-1] - base
		return ans


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		ans = 1
		x = 0
		target = [1] + target + [1]
		n = len(target)
		pre = 1
		while x < n - 1:
			while x < n and target[x] == 1:
				x += 1
			if x == n:
				break
			while x < n - 1 and target[x] <= target[x + 1]:
				x += 1
			_max = target[x]
			while x < n - 1 and target[x] >= target[x + 1]:
				x += 1
			_min = target[x]
			pre = _min
			ans += min(_max - pre, _max - 1)
		return ans


class Solution:

	def minNumberOperations(self, t: List[int]) -> int:
		cnt = t[0]
		for i in range(1, len(t)):
			if t[i] > t[i - 1]:
				cnt += t[i] - t[i - 1]
		return cnt


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		prev = 0
		total = 0
		for num in target:
			if num > prev:
				total += num - prev
			prev = num
		return total


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		prev = 0
		step = 0
		for i in range(len(target)):
			step += max(0, target[i] - prev)
			prev = target[i]
		return step


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		count = target[0]
		for (a, b) in zip(target, target[1:]):
			count += max(0, b - a)
		return count


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		(stack, count) = ([], 0)
		for x in target:
			m = 0
			while stack and stack[-1] >= x:
				m = max(m, stack.pop() - x)
			count += m
			stack.append(x)
		count += stack[-1]
		return count


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		if not target:
			return 0
		ret = target[0]
		for (a, b) in zip(target[:-1], target[1:]):
			ret += max(0, b - a)
		return ret


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		if not target:
			return 0
		totalCost = target[0]
		for index in range(1, len(target)):
			num = target[index]
			prev = target[index - 1]
			diff = num - prev
			totalCost += max(diff, 0)
		return totalCost
		lst = []
		lst.append(target)
		prev_layer = target
		new_layer = []
		while len(prev_layer) > 1:
			counter = 0
			while counter < len(prev_layer):
				fi = prev_layer[counter]
				se = fi
				if counter + 1 < len(prev_layer):
					se = prev_layer[counter + 1]
				new_layer.append(min(fi, se))
				counter += 2
			lst.append(new_layer)
			prev_layer = new_layer
			new_layer = []
		lst.append([0])
		cost = 0
		print(lst)
		for index in range(len(lst) - 2, -1, -1):
			l = lst[index]
			print(('l', l))
			for in_index in range(len(l)):
				val = l[in_index]
				parent_index = int(in_index / 2)
				cost += val - lst[index + 1][parent_index]
				print(('val', val))
				print(('parent_val', lst[index + 1][parent_index]))
				print(('cost', cost))
				print('--------')
		return cost


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		res = pre = 0
		for n in target:
			res += max(n - pre, 0)
			pre = n
		return res


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		(count, stack) = (0, [0])
		for height in target:
			if stack[-1] > height:
				while stack[-1] > height:
					stack.pop()
			else:
				count += height - stack[-1]
			stack.append(height)
		return count


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		ret = 0
		old = 0
		for e in target:
			if e > old:
				ret += e - old
			old = e
		return ret


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		stack = []
		ans = 0
		for n in target:
			if len(stack) != 0 and n <= stack[-1]:
				ans += stack[-1] - n
				while len(stack) != 0 and n <= stack[-1]:
					x = stack.pop()
			stack.append(n)
		if len(stack) != 0:
			ans += stack[-1]
		return ans


class Solution1:

	def minNumberOperations(self, target: List[int]) -> int:
		(max_bar, blocks) = (max(target), 0)
		for bar in range(1, max_bar + 1):
			op = [0] * len(target)
			prev_op = 0
			for (i, t) in enumerate(target):
				if t >= bar:
					op[i] = 1
				if prev_op != op[i]:
					prev_op = op[i]
					if op[i] == 1:
						blocks += 1
		return blocks

class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		(prev_t, n, valley) = (0, len(target), 0)
		blocks = 0
		for i in range(n):
			if i + 1 < n and target[i + 1] == target[i]:
				continue
			if prev_t < target[i] and (i + 1 == n or target[i] > target[i + 1]):
				blocks += target[i] - valley
			if target[i] < prev_t and (i + 1 == n or target[i] <= target[i + 1]):
				valley = target[i]
			prev_t = target[i]
		return blocks


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		l = target
		stack = []
		total = 0
		for i in range(len(l)):
			if stack and l[stack[-1]] > l[i]:
				total += l[stack[-1]] - l[i]
				while stack and l[stack[-1]] > l[i]:
					stack.pop()
			if not stack or l[stack[-1]] < l[i]:
				stack.append(i)
		if stack:
			total += l[stack[-1]]
		return total


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		stack = []
		count = 0
		target.append(0)
		for num in target:
			while stack and stack[-1] >= num:
				if len(stack) > 1:
					count += stack[-1] - max(num, stack[-2])
					stack.pop()
				else:
					count += stack.pop() - num
			stack.append(num)
		return count


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		ans = 0
		stack = [0]
		for num in target:
			max_ = 0
			while stack and stack[-1] >= num:
				max_ = max(max_, abs(stack.pop() - num))
			ans += max_
			stack.append(num)
		while stack[-1]:
			ans += abs(stack.pop() - stack[-1])
		return ans


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		bottleneck = 0
		ans = 0
		for num in target:
			if num > bottleneck:
				ans += num - bottleneck
				bottleneck = num
			else:
				bottleneck = num
		return ans


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		ans = 0
		stack = [0]
		for k in target:
			while len(stack) >= 1 and stack[-1] >= k:
				ans += stack[-1] - max(k, stack[-2])
				stack.pop()
			stack.append(k)
		return ans + stack[-1]


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		ret = target[0]
		for i in range(1, len(target)):
			ret += max(0, target[i] - target[i - 1])
		return ret


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		result = 0
		last = 0
		for i in range(len(target)):
			if target[i] >= last:
				result += target[i] - last
			last = target[i]
		return result


import heapq

class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		target.append(0)
		stack = [(0, -1)]
		ans = 0
		for (i, x) in enumerate(target):
			if stack[-1][0] < x:
				stack.append((x, i))
			elif stack[-1][0] == x:
				stack[-1] = (stack[-1][0], i)
			else:
				while len(stack) >= 2 and stack[-1][0] >= x:
					tmp = stack.pop()
					ans += tmp[0] - max(x, stack[-1][0])
					if stack[-1][0] > x:
						stack[-1] = (stack[-1][0], tmp[1])
				stack.append((x, i))
		return ans


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		res = 0
		cur = 0
		for i in range(len(target)):
			if target[i] > cur:
				res += target[i] - cur
			cur = target[i]
		return res


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		count = target[0]
		height = target[0]
		for val in target[1:]:
			if val > height:
				count += val - height
			height = val
		return count


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		res = 0
		prev = 0
		for t in target:
			res += max(t - prev, 0)
			prev = t
		return res


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		r = target[0]
		carry = target[0]
		for i in range(1, len(target)):
			if target[i] > carry:
				r += target[i] - carry
				carry = target[i]
			else:
				carry = target[i]
		return r


class Solution:

	def minNumberOperations(self, target: List[int]) -> int:
		r = carry = 0
		for h in target:
			if h > carry:
				r += h - carry
			carry = h
		return r