Given an array arr[] of size N. Find the maximum value of arr[j] – arr[i] + arr[l] – arr[k], such that i < j < k < l.
Example 1:
Input
N = 3
Arr[]  = {1, 2, 3}
Output:-1
Explanation: 
N<4 so no such i,j,k,l is possible.
 
Example 2:
Input:
N = 5
Arr[] = {4, 8, 9, 2, 20}
Output: 23
Explanation:
Here i = 0, j = 2, k = 3, l = 4 so
arr[j] – arr[i] + arr[l] – arr[k] 
= 9 – 4 + 20 – 2 = 23
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findMaxValue() which takes the array arr[] and its size N as input parameters and returns the maximum value of arr[j] – arr[i] + arr[l] – arr[k].
 
Expected Time Complexity : O(N)
Expected Auxiliary Space : O(N)
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    def findMaxValue(self, arr, n):

        # code here 

    

    

    

Solutions:
MIN = -100000000

class Solution:

	def findMaxValue(self, arr, n):
		if n < 4:
			return -1
		(table1, table2) = ([MIN] * (n + 1), [MIN] * n)
		(table3, table4) = ([MIN] * (n - 1), [MIN] * (n - 2))
		for i in range(n - 1, -1, -1):
			table1[i] = max(table1[i + 1], arr[i])
		for i in range(n - 2, -1, -1):
			table2[i] = max(table2[i + 1], table1[i + 1] - arr[i])
		for i in range(n - 3, -1, -1):
			table3[i] = max(table3[i + 1], table2[i + 1] + arr[i])
		for i in range(n - 4, -1, -1):
			table4[i] = max(table4[i + 1], table3[i + 1] - arr[i])
		return table4[0]


class Solution:

	def findMaxValue(self, arr, n):
		MIN = -10000000000
		if n < 4:
			return -1
		table1 = [0 for x in range(n + 2)]
		table2 = [0 for x in range(n + 2)]
		table3 = [0 for x in range(n + 2)]
		table4 = [0 for x in range(n + 2)]
		for i in range(n + 1):
			table1[i] = table2[i] = table3[i] = table4[i] = MIN
		for i in range(n - 1, -1, -1):
			table1[i] = max(table1[i + 1], arr[i])
		for i in range(n - 1, -1, -1):
			table2[i] = max(table2[i + 1], table1[i + 1] - arr[i])
		for i in range(n - 1, -1, -1):
			table3[i] = max(table3[i + 1], table2[i + 1] + arr[i])
		for i in range(n - 1, -1, -1):
			table4[i] = max(table4[i + 1], table3[i + 1] - arr[i])
		res = MIN
		for i in range(n):
			res = max(res, table4[i])
		return res


class Solution:

	def solve(self, arr, i, k, buy, dp):
		if k == 0:
			return 0
		if i >= len(arr):
			return -10000000
		if (i, k, buy) in dp:
			return dp[i, k, buy]
		if buy:
			dp[i, k, buy] = max(-arr[i] + self.solve(arr, i + 1, k, False, dp), self.solve(arr, i + 1, k, True, dp))
			return dp[i, k, buy]
		else:
			dp[i, k, buy] = max(arr[i] + self.solve(arr, i + 1, k - 1, True, dp), self.solve(arr, i + 1, k, False, dp))
			return dp[i, k, buy]

	def findMaxValue(self, arr, n):
		if n < 4:
			return -1
		(table1, table2) = ([-100000000] * (n + 1), [-1000000000] * n)
		(table3, table4) = ([-100000000] * (n - 1), [-1000000000] * (n - 2))
		for i in range(n - 1, -1, -1):
			table1[i] = max(table1[i + 1], arr[i])
		for i in range(n - 2, -1, -1):
			table2[i] = max(table2[i + 1], table1[i + 1] - arr[i])
		for i in range(n - 3, -1, -1):
			table3[i] = max(table3[i + 1], table2[i + 1] + arr[i])
		for i in range(n - 4, -1, -1):
			table4[i] = max(table4[i + 1], table3[i + 1] - arr[i])
		return table4[0]


class Solution:

	def findMaxValue(self, arr, n):
		if n < 4:
			return -1
		b1_0 = b1_1 = -arr[0]
		s1_0 = s1_1 = arr[1] + b1_0
		b2_0 = b2_1 = -arr[2] + s1_0
		s2_0 = s2_1 = arr[3] + b2_0
		for i in range(1, n):
			b1_1 = max(b1_0, -arr[i])
			if i >= 2:
				s1_1 = max(s1_0, b1_0 + arr[i])
			if i >= 3:
				b2_1 = max(b2_0, s1_0 - arr[i])
			if i >= 4:
				s2_1 = max(s2_0, b2_0 + arr[i])
			b1_0 = b1_1
			s1_0 = s1_1
			b2_0 = b2_1
			s2_0 = s2_1
		return s2_0


class Solution:

	def findMaxValue(self, arr, n):
		if n < 4:
			return -1
		ml = [0] * n
		ml[n - 1] = arr[-1]
		for i in range(n - 2, 2, -1):
			ml[i] = max(ml[i + 1], arr[i])
		mk = [0] * n
		mk[n - 2] = arr[-1] - arr[-2]
		for i in range(n - 3, 1, -1):
			mk[i] = max(mk[i + 1], ml[i + 1] - arr[i])
		mj = [0] * n
		mj[n - 3] = arr[-1] - arr[-2] + arr[-3]
		for i in range(n - 4, 0, -1):
			mj[i] = max(mj[i + 1], mk[i + 1] + arr[i])
		mi = [0] * n
		mi[n - 4] = arr[-1] - arr[-2] + arr[-3] - arr[-4]
		for i in range(n - 5, -1, -1):
			mi[i] = max(mi[i + 1], mj[i + 1] - arr[i])
		return mi[0]


class Solution:

	def findMaxValue(self, arr, n):
		if n < 4:
			return -1
		(dp1, dp2, dp3, dp4) = ([float('-inf')] * (n + 1), [float('-inf')] * n, [float('-inf')] * (n - 1), [float('-inf')] * (n - 2))
		for i in range(n - 1, -1, -1):
			dp1[i] = max(dp1[i + 1], arr[i])
		for i in range(n - 2, -1, -1):
			dp2[i] = max(dp2[i + 1], dp1[i + 1] - arr[i])
		for i in range(n - 3, -1, -1):
			dp3[i] = max(dp3[i + 1], dp2[i + 1] + arr[i])
		for i in range(n - 4, -1, -1):
			dp4[i] = max(dp4[i + 1], dp3[i + 1] - arr[i])
		return dp4[0]


class Solution:

	def findMaxValue(self, arr, n):
		if n < 4:
			return -1
		dp = [[-float('inf')] * n for i in range(4)]
		dp[0][0] = -arr[0]
		for i in range(1):
			for j in range(1, n - 3):
				dp[i][j] = max(dp[i][j - 1], -arr[j])
		for i in range(1, 4):
			for j in range(i, n - (4 - (i + 1))):
				if i == 1 or i == 3:
					dp[i][j] = max(arr[j] + dp[i - 1][j - 1], dp[i][j - 1])
				else:
					dp[i][j] = max(-arr[j] + dp[i - 1][j - 1], dp[i][j - 1])
		return dp[3][n - 1]