# Maximum sum obtained by dividing Array into several subarrays as per given conditions

Maximum sum obtained by dividing Array into several subarrays as per given conditionsGiven an array arr[] of size N, the task is to calculate the maximum sum that can be obtained by dividing the array into several subarrays(possibly one), where each subarray starting at index i and ending at index j (j>=i) contributes arr[j]-arr[i] to the sum.Examples:Input: arr[]= {1, 5, 3}, N=3Output: 4Explanation: The array can be divided into 2 subarrays:{1, 5} -> sum contributed by the subarray = 5-1 = 4{3} -> sum contributed by the subarray = 3-3 = 0Therefore, the answer is 4.(It can be shown that there is no other way of dividing this array in multiple subarrays such that the answer is greater than 4).Input: arr[] = {6, 2, 1}, N=3Output:0Naive Approach: The naive approach is to consider all possible ways of dividing arr into 1 or more subarrays and calculating the maximum sum obtained for each.Time Complexity: O(N*2N)Auxiliary Space: O(1)Observation: The observations necessary to solve the problem are below:The array should be divided into several(possibly one) subarrays such that each subarray is the longest increasing subarray. For example, if arr[]={3,5,7,9,1}, it is optimal to consider {3,5,7,9} as a subarray as it would contribute 9-3=6 to the sum. Breaking it up further decreases the sum which is not optimal.Every element of a non-increasing subarray should be considered as single element subarrays so that they contribute 0 to the sum. Otherwise, they would be contributing a negative value. For example, if arr[i]>arr[i+1], it is optimal to consider two subarrays of length 1 containing arr[i] and arr[i+1] separately, so that they contribute (arr[i]-arr[i]) +(arr[i+1]-arr[i+1]) =0 to the answer. If they were considered together, they would contribute arr[i+1]-arr[i] which is a negative number, thus decreasing the sum.Efficient Approach: Follow the steps below to solve the problem:Initialize a variable Sum to 0.Traverse arr from 1 to N-1, using the variable i, and do the following:If arr[i]>arr[i-1], add arr[i]-arr[i-1] to Sum. This works because the sum of differences of adjacent elements in a sorted array is equal to the difference of the elements at extreme ends. Here, only the increasing subarrays are considered as arr[i]>arr[i-1].Below is the implementation of the above approach:C++#include using namespace std;  int maximumSum(int arr[], int N){        int Sum = 0;    for (int i = 1; i < N; i++) {                          if (arr[i] > arr[i – 1])            Sum += (arr[i] – arr[i – 1]);    }    return Sum;}int main(){        int arr[] = { 1, 5, 3 };    int N = (sizeof(arr) / (sizeof(arr)));          cout 