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

Question

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 
    // of adjacent elements 
    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[0]; 
    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[0]); 

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

return 0; 
} 

Answer 1

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<j} (a_j-a_i) = \max_{i<j} b_i + \cdots + b_{j-1}. $$