1
$\begingroup$

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; 
} 
$\endgroup$
  • $\begingroup$ This is not a coding site! Can you replace the code with pseudocode? $\endgroup$ – Yuval Filmus Apr 2 at 13:30
0
$\begingroup$

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}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.