Geek has an array Arr, where Arr[i] (1-based indexing) denotes the number of chocolates corresponding to each station. When he moves from station i to station i+1 he gets A[i]  A[i+1] chocolates for free, if this number is negative, he looses that many chocolates also.
He can only move from station i to station i+1, if he has non-negative number of chocolates with him.
Given the cost of one chocolate Rs. P. Find the minimum cost incurred in reaching last station from the first station (station 1).
Note: Initially Geek has 0 chocolates.
 
Example 1:
Input:
N=3, price=10
arr[] = { 1, 2, 3 }
Output:  30
Explanation: 
To reach the first station from the starting
point, we need to buy 1 chocolate,To reach 
station 2 form station 1, we get A[1]  A[2]
= -1 chocolates i.e. we lose 1 chocolate. 
Hence, we need to buy 1 chocolate.Similarly, 
we need to buy 1 chocolate to reach station 3
from station 2.
Hence, total cost incurred = (1+1+1)*10 = 30
 
Example 2:
Input:
N=6, price=5
arr[] = { 10, 6, 11, 4, 7, 1 }
Output:  55
Explanation: 
To reach to the first station from starting
point he need to buy 10 chocolates. 
Chocolates Bought = 10,Chocolates balance = 0
On reaching second station he will get 
(10-6)= 4 chocolates.
Chocolates Bought= 10 , Chocolates balance = 4.
To reach to 3 station , he has to buy (6- 11) 
= 5 chocolates.But he has 4 chocolates as balance. 
So the chocolates he need to buy is (5 -4 ) =1;
Chocolates Bought= 11 , Chocolates balance = 0.
On reaching station 4 , he will get (11 - 4)= 7 
chocolates.
Chocolates Bought= 11 , Chocolates balance = 7.
To reach to 5 station , he has to buy (4- 7)= 3 
chocolates.
But he has 7 chocolates as balance .
Chocolates Bought= 11 , Chocolates balance = 4.
To reach to 6 station , he will get (7- 1) = 6
chocolates. 
Chocolates Bought= 11 , Chocolates balance = 10.
Therefore, total chocolates he has to buy is 11.
Hence, Amount=11*5=55.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function getChocolateCost() that takes array arr and an integer chocolateMRP as parameters and returns the minimum cost.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3







def getChocolateCost(arr,chocolateMRP):

    

Solutions:
def getChocolateCost(arr, chocolateMRP):
	ch_bou = arr[0]
	ch_bal = 0
	for i in range(n - 1):
		ch_bou1 = 0
		if arr[i] - arr[i + 1] > 0:
			ch_bal = ch_bal + (arr[i] - arr[i + 1])
		if arr[i] - arr[i + 1] < 0:
			ch_bal = ch_bal - (arr[i + 1] - arr[i])
		if ch_bal < 0:
			ch_bou1 = -ch_bal
			ch_bou = ch_bou1 + ch_bou
			ch_bal = 0
	totalcost = ch_bou * chocolateMRP
	return totalcost


def getChocolateCost(arr, chocolateMRP):
	(bought, balance) = (arr[0], 0)
	for index in range(n - 1):
		(current, nxt) = (arr[index], arr[index + 1])
		diff = current - nxt
		balance += diff
		if balance < 0:
			buy = -balance
			bought += buy
			balance = 0
	return bought * chocolateMRP


def getChocolateCost(arr, p):
	return max(arr) * p


def getChocolateCost(arr, cost):
	cho = 0
	m = arr[0]
	for i in range(len(arr) - 1):
		temp = arr[i] - arr[i + 1]
		cho += temp
		if cho < 0:
			m += -cho
			cho = 0
	return m * cost


def getChocolateCost(arr, chocolateMRP):
	return max(arr) * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	n = len(arr)
	chocbut = arr[0]
	currchoc = 0
	for i in range(0, n - 1):
		choc = arr[i] - arr[i + 1]
		currchoc += choc
		if currchoc < 0:
			chocbut += abs(currchoc)
			currchoc = 0
	return chocbut * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	n = len(arr)
	ans = 0
	if arr[0] > 0:
		ans = arr[0]
	h = 0
	for i in range(0, n - 1):
		c = h + arr[i] - arr[i + 1]
		if c < 0:
			ans += abs(c)
			h = 0
		else:
			h = c
	return chocolateMRP * ans


def getChocolateCost(arr, price):
	balance = 0
	bought = arr[0]
	for i in range(1, n):
		if arr[i] >= arr[i - 1]:
			val = arr[i] - arr[i - 1]
			if val >= balance:
				bought += val - balance
				balance = 0
			else:
				balance = balance - val
		else:
			balance += arr[i - 1] - arr[i]
	return bought * price


def getChocolateCost(arr, chocolateMRP):
	cb = arr[0]
	cbb = 0
	for i in range(1, len(arr)):
		if arr[i] - arr[i - 1] > 0:
			if cbb - (arr[i] - arr[i - 1]) < 0:
				cb += arr[i] - arr[i - 1] - cbb
				cbb = 0
			else:
				cbb -= arr[i] - arr[i - 1]
		else:
			cbb += arr[i - 1] - arr[i]
	return cb * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	balance = 0
	bought = arr[0]
	required = 0
	i = 0
	j = 1
	while j < n:
		required = arr[i] - arr[j]
		if required > 0:
			balance += required
		elif balance > -1 * required:
			balance = balance + required
		else:
			bought += -1 * (balance + required)
			balance = 0
		i += 1
		j += 1
	return bought * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	n = len(arr)
	choc_buy = arr[0]
	curr_choc = 0
	for i in range(0, n - 1):
		choc = arr[i] - arr[i + 1]
		curr_choc += choc
		if curr_choc < 0:
			choc_buy += abs(curr_choc)
			curr_choc = 0
	return choc_buy * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	(bought, balance) = (arr[0], 0)
	for i in range(len(arr) - 1):
		if arr[i + 1] <= arr[i]:
			balance += arr[i] - arr[i + 1]
		elif balance >= arr[i + 1] - arr[i]:
			balance -= arr[i + 1] - arr[i]
		else:
			bought = bought + arr[i + 1] - arr[i] - balance
			balance = 0
	return bought * chocolateMRP


def getChocolateCost(arr, p):
	choc_buy = arr[0]
	curr_choc = 0
	for i in range(n - 1):
		choc_needed = arr[i] - arr[i + 1]
		if choc_needed > 0:
			curr_choc = curr_choc + choc_needed
		elif choc_needed < 0:
			if curr_choc >= abs(choc_needed):
				curr_choc = curr_choc - abs(choc_needed)
			else:
				choc_buy = abs(curr_choc + choc_needed) + choc_buy
				curr_choc = 0
		else:
			pass
	return choc_buy * p


def getChocolateCost(arr, chocolateMRP):
	total_buy = arr[0]
	bal = 0
	for i in range(len(arr) - 1):
		curr = arr[i] - arr[i + 1]
		bal += curr
		if bal < 0:
			total_buy += abs(bal)
			bal = 0
	return total_buy * chocolateMRP
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	ans = getChocolateCost(a, k)
	print(ans)


def getChocolateCost(arr, chocolateMRP):
	arr = sorted(arr)
	return arr[-1] * chocolateMRP
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	ans = getChocolateCost(a, k)
	print(ans)


def getChocolateCost(arr, chocolateMRP):
	need_to_buy = arr[0]
	free_cho = 0
	for i in range(n - 1):
		if arr[i] - arr[i + 1] > 0:
			free_cho = free_cho + arr[i] - arr[i + 1]
		elif free_cho + (arr[i] - arr[i + 1]) <= 0:
			diff = abs(free_cho + (arr[i] - arr[i + 1]))
			need_to_buy += diff
			free_cho = 0
		else:
			free_cho = free_cho + (arr[i] - arr[i + 1])
	return need_to_buy * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	purchased = 0
	chocBalance = 0
	for i in range(len(arr)):
		if i == 0:
			purchased += arr[i]
			continue
		diff = arr[i - 1] - arr[i]
		chocBalance += diff
		if chocBalance < 0:
			purchased = purchased - chocBalance
			chocBalance = 0
	return purchased * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	buy = a[0]
	balance = 0
	for i in range(0, n - 1):
		curr = a[i]
		nextt = a[i + 1]
		if nextt < curr:
			balance = balance + (curr - nextt)
		elif balance >= nextt - curr:
			balance = balance - (nextt - curr)
		else:
			val = nextt - curr - balance
			buy = buy + val
			balance = balance - (nextt - curr) + val
	return buy * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	cbuy = arr[0]
	cbal = 0
	for i in range(1, len(arr)):
		bal = arr[i - 1] - arr[i]
		if bal >= 0:
			cbal += bal
		elif cbal >= abs(bal):
			cbal -= abs(bal)
		else:
			cbuy += abs(bal) - cbal
			cbal = 0
	return chocolateMRP * cbuy


def getChocolateCost(arr, chocolateMRP):
	n = len(arr)
	mx = arr[0]
	for i in range(1, n):
		if mx < arr[i]:
			mx = arr[i]
	return mx * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	arr.sort()
	return arr[len(arr) - 1] * chocolateMRP


def getChocolateCost(arr, MRP):
	buyc = arr[0]
	curr = 0
	n = len(arr)
	for i in range(n - 1):
		if curr + arr[i] > arr[i + 1]:
			curr += arr[i] - arr[i + 1]
		else:
			buyc += abs(curr + arr[i] - arr[i + 1])
			curr = 0
	return buyc * MRP


def getChocolateCost(arr, chocolateMRP):
	c_gained = 0
	c_bought = a[0]
	for i in range(0, len(arr) - 1):
		c_gained += a[i] - a[i + 1]
		if c_gained < 0:
			c_bought += abs(c_gained)
			c_gained = 0
	return c_bought * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	n = len(arr)
	buy = arr[0]
	a = 0
	for i in range(1, n):
		a += arr[i - 1] - arr[i]
		if a < 0:
			buy += abs(a)
			a = 0
	return buy * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	n = len(arr)
	buy = arr[0]
	total = 0
	for i in range(1, n):
		cost = arr[i - 1] - arr[i]
		total += cost
		if total < 0:
			buy += abs(total)
			total = 0
	return buy * chocolateMRP


def getChocolateCost(arr, p):
	n = len(arr)
	buy = arr[0]
	curr = 0
	for i in range(1, n):
		cost = arr[i - 1] - arr[i]
		curr += cost
		if curr < 0:
			buy += abs(curr)
			curr = 0
	return buy * p


def getChocolateCost(arr, chocolateMRP):
	c = arr[0]
	m = 0
	for j in range(1, len(arr)):
		if arr[j - 1] - arr[j] >= 0:
			m += arr[j - 1] - arr[j]
		elif arr[j] - arr[j - 1] <= m:
			m = m - (arr[j] - arr[j - 1])
		else:
			c = c + (arr[j] - arr[j - 1]) - m
			m = 0
	return c * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	bought = abs(-arr[0])
	choco = 0
	for i in range(1, len(arr)):
		choco += arr[i - 1] - arr[i]
		if choco < 0:
			bought += abs(choco)
			choco = 0
	return bought * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	ans = arr[0]
	n = len(arr)
	res = 0
	for i in range(0, n - 1):
		res_now = arr[i] - arr[i + 1]
		res += res_now
		if res < 0:
			ans += abs(res)
			res = 0
	return ans * chocolateMRP


def getChocolateCost(a, bp):
	cb = a[0]
	c = 0
	p = 0
	for i in range(len(a) - 1):
		if a[i] - a[i + 1] > 0:
			c += a[i] - a[i + 1]
		else:
			p = c + a[i] - a[i + 1]
			if p < 0:
				cb += -p
				c = 0
			else:
				c = p
	return cb * bp


def getChocolateCost(arr, chocolateMRP):
	arr = sorted(arr)
	return arr[len(arr) - 1] * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	ans = arr[0]
	a = 0
	for i in range(1, len(arr)):
		d = arr[i - 1] - arr[i]
		a += d
		if a < 0:
			ans += -a
			a = 0
	return ans * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	bought = arr[0]
	balance = 0
	for i in range(len(arr) - 1):
		x = arr[i] - arr[i + 1]
		balance += x
		if balance < 0:
			bought -= balance
			balance = 0
	return bought * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	choc = -arr[0]
	ret = 0
	if choc < 0:
		ret += -chocolateMRP * choc
		choc = 0
	for i in range(len(arr) - 1):
		choc += arr[i] - arr[i + 1]
		if choc < 0:
			ret += -chocolateMRP * choc
			choc = 0
	return ret


def getChocolateCost(arr, chocolateMRP):
	n = len(arr)
	bought = arr[0]
	balance = 0
	for i in range(1, n):
		cn = arr[i - 1] - arr[i]
		balance += cn
		if balance < 0:
			bought += abs(balance)
			balance = 0
	return bought * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	ans = arr[0]
	cb = 0
	for i in range(len(arr) - 1):
		if arr[i] < arr[i + 1]:
			if cb < abs(arr[i] - arr[i + 1]):
				ans += abs(cb - abs(arr[i] - arr[i + 1]))
				cb = 0
			else:
				cb -= abs(arr[i] - arr[i + 1])
		else:
			cb += arr[i] - arr[i + 1]
	return ans * chocolateMRP


def getChocolateCost(arr, chocolateMRP):
	nc = 0
	req = 0
	for i in range(len(arr) - 1):
		x = arr[i] - arr[i + 1]
		if x > 0:
			nc = nc + x
		elif x < 0:
			x = x * -1
			if nc >= x:
				nc = nc - x
			else:
				x = x - nc
				nc = 0
				req = req + x * chocolateMRP
	req = req + arr[0] * chocolateMRP
	return req