Consider a devotee wishing to give offerings to temples along a mountain range. The temples are located in a row at different heights. Devotee is very religious and wants to offer each temple at least one offering. If two adjacent temples are at different altitudes, then the temple that is higher up should receive more offerings than the one that is at lower altitude. If two adjacent temples are at the same height, then their offerings relative to each other does not matter. The height of the N temples are given in the array arr[]. Find the minimum number of offerings required.
 
Example 1:
Input: N = 3
arr = {1, 2, 2}
Output: 4
Explaination: Bring 1 offering each for 
first and third temple and 2 offerings 
for the second temple.
 
Example 2:
Input: N = 6
arr = {1, 4, 3, 6, 2, 1}
Output: 10
Explaination: 
1 offering each for 1st, 3rd and 6th temple, 
2 offerings each for 2nd and 5th temple and 
3 offerings for the 4th temple.
 
Your Task:
You do not need to take input or print anything. Your task is to complete the function offerings() which takes the value N and arr[] as input parameters and returns the minimum number of offerings required.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 ≤ N ≤ 10^{4}
1 ≤ arr[ i ] ≤ 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def offerings(self, N, arr):
        # code here

Solutions:
class Solution:

	def offerings(self, N, arr):
		l = [0] * N
		r = [0] * N
		l[0] = 1
		r[-1] = 1
		for i in range(1, len(arr)):
			if arr[i] > arr[i - 1]:
				l[i] = l[i - 1] + 1
			else:
				l[i] = 1
		for i in range(N - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				r[i] = r[i + 1] + 1
			else:
				r[i] = 1
		count = 0
		for i in range(N):
			count += max(l[i], r[i])
		return count


class Temple:

	def __init__(self, l: int, r: int):
		self.L = l
		self.R = r

class Solution:

	def offerings(self, n, templeHeight):
		chainSize = [0] * n
		for i in range(n):
			chainSize[i] = Temple(-1, -1)
		chainSize[0].L = 1
		chainSize[-1].R = 1
		for i in range(1, n):
			if templeHeight[i - 1] < templeHeight[i]:
				chainSize[i].L = chainSize[i - 1].L + 1
			else:
				chainSize[i].L = 1
		for i in range(n - 2, -1, -1):
			if templeHeight[i + 1] < templeHeight[i]:
				chainSize[i].R = chainSize[i + 1].R + 1
			else:
				chainSize[i].R = 1
		sm = 0
		for i in range(n):
			sm += max(chainSize[i].L, chainSize[i].R)
		return sm


class Solution:

	def get_arr(self, arr, i):
		if i < 0:
			return arr[0]
		elif i >= len(arr):
			return arr[-1]
		return arr[i]

	def get_price(self, arr, fin, i):
		if fin[i] != -1:
			return fin[i]
		if i < 0 or i >= len(arr):
			return 0
		prev = self.get_arr(arr, i - 1)
		cur = self.get_arr(arr, i)
		nxt = self.get_arr(arr, i + 1)
		go = 0
		if prev < cur and cur > nxt:
			go = max(self.get_price(arr, fin, i - 1), self.get_price(arr, fin, i + 1)) + 1
		elif prev < cur == nxt:
			go = self.get_price(arr, fin, i - 1) + 1
		elif prev < cur < nxt:
			go = self.get_price(arr, fin, i - 1) + 1
		elif prev == cur > nxt:
			go = self.get_price(arr, fin, i + 1) + 1
		elif prev == cur == nxt:
			go = 1
		elif prev == cur < nxt:
			go = 1
		elif prev > cur > nxt:
			go = self.get_price(arr, fin, i + 1) + 1
		elif prev > cur == nxt:
			go = 1
		elif prev > cur < nxt:
			go = 1
		fin[i] = go
		return go

	def offerings(self, N, arr):
		if len(arr) == 1:
			return 1
		fin = [-1] * len(arr)
		ans = 0
		for i in range(len(arr)):
			ans += self.get_price(arr, fin, i)
		return ans


class Solution:

	def offerings(self, N, arr):
		ratings = arr
		l = [1 for _ in range(len(ratings))]
		r = [1 for _ in range(len(ratings))]
		for i in range(1, len(ratings)):
			if ratings[i] > ratings[i - 1]:
				l[i] = l[i - 1] + 1
		j = len(ratings) - 2
		while j >= 0:
			if ratings[j] > ratings[j + 1]:
				r[j] = r[j + 1] + 1
			j -= 1
		return sum([max(l[i], r[i]) for i in range(len(ratings))])


class Solution:

	def offerings(self, N, nums):
		dp = [1] * N
		for i in range(1, N):
			if nums[i] > nums[i - 1]:
				dp[i] = dp[i - 1] + 1
			else:
				dp[i] = 1
		for i in range(N - 2, -1, -1):
			if nums[i] > nums[i + 1]:
				dp[i] = max(dp[i], dp[i + 1] + 1)
			else:
				dp[i] = max(dp[i], 1)
		return sum(dp)


class Solution:

	def offerings(self, N, arr):
		rightmat = [0 for i in range(N)]
		leftmat = [0 for i in range(N)]
		sum = 0
		rightmat[0] = leftmat[-1] = 1
		for i in range(1, N):
			if arr[i] > arr[i - 1]:
				rightmat[i] = rightmat[i - 1] + 1
			else:
				rightmat[i] = 1
		for i in range(N - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				leftmat[i] = leftmat[i + 1] + 1
			else:
				leftmat[i] = 1
		for i in range(N):
			sum += max(leftmat[i], rightmat[i])
		return sum


class Solution:

	def offerings(self, N, arr):
		dp = [[1, 1] for i in range(len(arr))]
		for i in range(1, len(arr)):
			if arr[i] > arr[i - 1]:
				dp[i][0] = dp[i - 1][0] + 1
			else:
				dp[i][0] = 1
		for i in range(len(arr) - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				dp[i][1] = dp[i + 1][1] + 1
			else:
				dp[i][1] = 1
		ans = 0
		for j in range(len(arr)):
			ans += max(dp[j])
		return ans


class Solution:

	def offerings(self, N, arr):
		ans = [1 for i in range(N)]
		for i in range(1, N):
			if arr[i] > arr[i - 1]:
				ans[i] = ans[i - 1] + 1
		for i in range(N - 2, -1, -1):
			if arr[i] > arr[i + 1] and ans[i] <= ans[i + 1]:
				ans[i] = ans[i + 1] + 1
		return sum(ans)


class Solution:

	def offerings(self, N, arr):
		fw = [0]
		bw = [0 for i in range(N)]
		curr = 0
		for i in range(1, N):
			if arr[i] <= arr[i - 1]:
				curr = 0
				fw.append(curr)
			else:
				curr += 1
				fw.append(curr)
		curr = 0
		for i in range(N - 2, -1, -1):
			if arr[i] <= arr[i + 1]:
				curr = 0
				bw[i] = curr
			else:
				curr += 1
				bw[i] = curr
		total_offers = 0
		for i in range(N):
			total_offers += max(fw[i], bw[i]) + 1
		return total_offers


import numpy as np

class Solution:

	def offerings(self, N, arr):
		Larr = [1] * N
		Rarr = [1] * N
		for i in range(1, len(arr)):
			if arr[i - 1] < arr[i]:
				Larr[i] = Larr[i - 1] + 1
			else:
				Larr[i] = 1
		for i in range(len(arr) - 2, -1, -1):
			if arr[i + 1] < arr[i]:
				Rarr[i] = Rarr[i + 1] + 1
			else:
				Rarr[i] = 1
		ret = []
		for i in range(len(Larr)):
			ret.append(max(Larr[i], Rarr[i]))
		return np.sum(ret)


class Solution:

	def offerings(self, N, arr):
		if N == 1:
			return 1
		left = [1] * N
		right = [1] * N
		ans = 0
		for i in range(1, N):
			if arr[i] > arr[i - 1]:
				left[i] = left[i - 1] + 1
		for i in range(N - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				right[i] = right[i + 1] + 1
		for i in range(N):
			ans += max(left[i], right[i])
		return ans


class Solution:

	def offerings(self, n, arr):
		ans = 0
		arrl = [0 for i in range(n)]
		arrr = [0 for i in range(n)]
		arrl[0] = 1
		for i in range(1, n):
			if arr[i] <= arr[i - 1]:
				arrl[i] = 1
			else:
				arrl[i] = arrl[i - 1] + 1
		arrr[-1] = 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				arrr[i] = 1 + arrr[i + 1]
			else:
				arrr[i] = 1
		return sum([max(i, j) for (i, j) in zip(arrl, arrr)])


class Solution:

	def offerings(self, N, arr):
		off = [1] * N
		for i in range(1, N):
			if arr[i] > arr[i - 1]:
				off[i] = off[i - 1] + 1
		for i in range(N - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				off[i] = max(off[i + 1] + 1, off[i])
		return sum(off)


def templeOffrings(arr):
	n = len(arr)
	dpLTR = [0 for i in arr]
	dpRTL = [0 for i in arr]
	dpLTR[0] = 1
	dpRTL[n - 1] = 1
	for i in range(1, n):
		if arr[i - 1] < arr[i]:
			dpLTR[i] = 1 + dpLTR[i - 1]
		else:
			dpLTR[i] = 1
	for i in range(n - 2, -1, -1):
		if arr[i + 1] < arr[i]:
			dpRTL[i] = 1 + dpRTL[i + 1]
		else:
			dpRTL[i] = 1
	return sum([max(dpRTL[i], dpLTR[i]) for i in range(n)])

class Solution:

	def offerings(self, N, arr):
		return templeOffrings(arr)


class Solution:

	def offerings(self, N, ans):
		count = 0
		left = [-1 for i in range(N)]
		left[0] = 1
		for i in range(1, N):
			if ans[i] > ans[i - 1]:
				left[i] = left[i - 1] + 1
			else:
				left[i] = 1
		right = [-1 for i in range(N)]
		right[N - 1] = 1
		for i in range(N - 2, -1, -1):
			if ans[i] > ans[i + 1]:
				right[i] = right[i + 1] + 1
			else:
				right[i] = 1
		res = [-1 for i in range(N)]
		count = 0
		for i in range(N):
			res[i] = max(left[i], right[i])
			count += res[i]
		return count


class Solution:

	def offerings(self, n, arr):
		prev = arr[0]
		start = 0
		profit = 0
		dp1 = [0] * n
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				profit = i - start
			else:
				start = i
				profit = 0
			dp1[i] = profit
		prev = arr[n - 1]
		start = n - 1
		profit = 0
		dp2 = [0] * n
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				profit = start - i
			else:
				start = i
				profit = 0
			dp2[i] = profit
		ans = 0
		for i in range(n):
			ans += max(dp1[i], dp2[i]) + 1
		return ans


class Solution:

	def offerings(self, N, a):
		ans = []
		left = [1] * N
		right = [1] * N
		for i in range(1, N):
			j = N - 1 - i
			if a[i] > a[i - 1]:
				left[i] = left[i - 1] + 1
			if a[j] > a[j + 1]:
				right[j] = right[j + 1] + 1
		ans = 0
		for i in range(N):
			select = max(right[i], left[i])
			ans = ans + select
		return ans
		d = {}
		print(right)
		print(left)
		return 0


class Solution:

	def offerings(self, N, arr):
		memo = [0] * N
		memo[0] = 1
		memo[N - 1] = 1
		for i in range(1, N):
			if arr[i] > arr[i - 1]:
				memo[i] = memo[i - 1] + 1
			elif arr[i] == arr[i - 1]:
				memo[i] = 1
			else:
				memo[i] = 1
		for i in range(N - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				temp = memo[i + 1] + 1
				memo[i] = max(memo[i], temp)
			elif arr[i] == arr[i + 1]:
				temp = 1
				memo[i] = max(memo[i], temp)
			else:
				temp = 1
				memo[i] = max(memo[i], temp)
		return sum(memo)


class tem:

	def __init__(self, lt, rt):
		self.L = lt
		self.R = rt

class Solution:

	def offerings(self, N, arr):
		dp = [0 for i in range(N)]
		res = 0
		for i in range(N):
			dp[i] = tem(-1, -1)
		dp[0].L = 1
		dp[-1].R = 1
		for i in range(1, N):
			if arr[i] > arr[i - 1]:
				dp[i].L = dp[i - 1].L + 1
			else:
				dp[i].L = 1
		for i in range(N - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				dp[i].R = dp[i + 1].R + 1
			else:
				dp[i].R = 1
		for i in range(N):
			res += max(dp[i].L, dp[i].R)
		return res


class Solution:

	def offerings(self, N, arr):
		left = [0] * N
		left[0] = 1
		for i in range(1, N):
			if arr[i] > arr[i - 1]:
				left[i] = left[i - 1] + 1
			else:
				left[i] = 1
		right = [0] * N
		right[N - 1] = 1
		s = 0
		for i in range(N - 1, -1, -1):
			if i < N - 1 and arr[i] > arr[i + 1]:
				right[i] = right[i + 1] + 1
			else:
				right[i] = 1
			s += max(left[i], right[i])
		return s