Given an array arr of size N, the task is to modify values of this array in such a way that the sum of absolute differences between two consecutive elements is maximized. If the value of an array element is X, then we can change it to either 1 or X. Find the maximum possible value of the sum of absolute differences between two consecutive elements.
Example 1:
Input: N = 4, arr[] = [3, 2, 1, 4, 5]
Output: 8
Explanation: We can modify above array as
arr[] = [3, 1, 1, 4, 1]
Sum of differences = 
|1-3| + |1-1| + |4-1| + |1-4| = 8
Which is the maximum obtainable value 
among all choices of modification.
Example 2:
Input: N = 2, arr[] = {1, 5}
Output: 4
Explanation: No modification required
Your Task:  
You don't need to read input or print anything. Complete the function maximumDifferenceSum() which takes N and array arr as input parameters and returns the integer value
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3
class Solution:
	def maximumDifferenceSum(self,arr, N):
		# code here

Solutions:
class Solution:

	def maximumDifferenceSum(self, arr, N):
		dp = [[0] * 2 for i in range(N)]
		for i in range(1, N):
			dp[i][0] = max(dp[i - 1][0] + abs(arr[i] - arr[i - 1]), dp[i - 1][1] + abs(arr[i] - 1))
			dp[i][1] = max(dp[i - 1][0] + abs(1 - arr[i - 1]), dp[i - 1][1])
		return max(dp[-1])