# Why finding the difference between the adjacent elements of the array to find the maximum difference?

I want to understand a tricky method to find the maximum difference between two elements such that larger element appears after the smaller number. I found easy solution keeping track of the minimum array but I don't get the following solution which first find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. The problems turns into finding the maximum sum subarray of this difference array.

Here is a working example plus my comments showing where I especially don't understand the algorithm.

// C++ program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
#include <bits/stdc++.h>
using namespace std;

/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
int maxDiff(int arr[], int n)
{
// Create a diff array of size n-1.
// The array will hold the difference
int diff[n-1];
for (int i=0; i < n-1; i++)
diff[i] = arr[i+1] - arr[i];

// Now find the maximum sum
// subarray in diff array
int max_diff = diff;
for (int i=1; i<n-1; i++)
{
if (diff[i-1] > 0)
diff[i] += diff[i-1]; // I especially don't get why we add differences
if (max_diff < diff[i])
max_diff = diff[i]; // and why we update the max_diff as the sum of differences
}
return max_diff;
}

/* Driver program to test above function */
int main()
{
int arr[] = {80, 2, 6, 3, 100};
int n = sizeof(arr) / sizeof(arr);

// Function calling
cout << "Maximum difference is " << maxDiff(arr, n);

return 0;
}

• This is not a coding site! Can you replace the code with pseudocode? – Yuval Filmus Apr 2 '19 at 13:30

Suppose that the original array is $$a_1,\ldots,a_n$$. The new array is $$b_i = a_{i+1} - a_i$$ for $$1 \leq i \leq n-1$$. Note that $$a_j - a_i = b_i + \cdots + b_{j-1}.$$ Hence $$\max_{\substack{i < j \\ a_i < a_j}} |a_j-a_i| = \max_{i