We have an array a[] of N stones of various heights laid out in a row. By taking some consecutive section of the stones, we wish to form a pyramid, where the height of the stones start from 1, increase by 1, until it reaches some value x, then decreases by 1 until it reaches 1 again i.e. the stones should be 1, 2, 3, 4…x – 1, x, x – 1, x – 2 … 1. All other stones not part of the pyramid should have a height 0. We cannot move any of the stones from their current position, however, by paying a fee of 1, we can reduce the heights of the stones. We wish to minimize the cost of building a pyramid. Output the minimum cost to build this pyramid. Assume that always a pyramid would be made of the input elements.
 
Example 1: 
Input:
N = 6
a[] = {1, 2, 3, 4, 2, 1}
Output:
4
Explanation:
We can obtain the array {1, 2, 3, 2, 1, 0}
by substracting 2 out of 4, 1 out of 2,
and 1 out of 1. In total, we will substract 4.
Example 2: 
Input:
N = 3
a[] = {1, 2, 1}
Output:
0
Explanation:
The array is already in Pyramid form.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function pyramidForm() which takes an Integer N and an array a[] as input and returns the minimum cost.
 
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{5}
1 <= a[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def pyramidForm(self, a, N):

        # code here 

Solutions:
class Solution:

	def pyramidForm(self, a, N):
		a = list(a)
		dp1 = [0] * N
		dp2 = [0] * N
		dp1[0] = min(1, a[0])
		for i in range(1, N):
			dp1[i] = min(i + 1, dp1[i - 1] + 1, a[i])
		dp2[N - 1] = min(1, a[N - 1])
		for i in range(N - 2, -1, -1):
			dp2[i] = min(N - i, a[i], dp2[i + 1] + 1)
		dp = [0] * N
		for i in range(N):
			dp[i] = min(dp1[i], dp2[i])
		mi = 0
		for i in range(N):
			if dp[i] > dp[mi]:
				mi = i
		c = 0
		h = dp[mi]
		for i in range(mi, -1, -1):
			c += a[i] - h
			if h > 0:
				h -= 1
		h = dp[mi] - 1
		for i in range(mi + 1, N):
			c += a[i] - h
			if h > 0:
				h -= 1
		return c


class Solution:

	def pyramidForm(self, arr, n):
		left = [0] * n
		right = [0] * n
		arr = list(arr)
		left[0] = 1
		for i in range(1, n):
			left[i] = min(arr[i], left[i - 1] + 1)
		right[-1] = 1
		for i in range(n - 2, -1, -1):
			right[i] = min(arr[i], right[i + 1] + 1)
		mini = float('inf')
		summe = sum(arr)
		for i in range(n):
			curr = summe - min(left[i], right[i]) ** 2
			mini = min(mini, curr)
		return mini