Find the Maximum Difference

See the original problem on HackerRank.

You are given a sequence of integers S, your task is to find a pair i,j of indices with i<j that maximizes the difference S[j]-S[i].

Note that what makes this challenge more interesting is the requirement of order, that i < j (without it you simply need to find the maximum and minimum element of S).

You have to output the value of the maximum difference.

Input Format

An integer N followed by N space separated integers S[i] on a new line.

Constraints

1 < N <= 10^6
0 <= S[i] <= 10^4

Output Format

The maximum difference as an integer.

Solutions

This problem has a naive quadratic solution that involves considering every pairs \(i,j\) with \(j>i\) and tracking the maximum. What makes this naive is that it is a bruce force solution that does not consider the input domain or the structure of the problem.

To see the solution, consider what pairs we should consider for the index \(j\). Let’s suppose that \(j\) is the right hand index so we need only look at elements of \(S\) that precede \(j\). The difference \(s[j]-s[i]\) is maximized for the index \(i\) that contains the minimum element of \(s[1],…s[j-1]\).

Therefore, instead of looking over pairs, we need only to keep track of the maximum element preceding any other index. This is linear.

Here is a possible C++ implementation of the described idea:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


int find_max_diff(const vector<int>& in)
{
	auto max = numeric_limits<int>::min();
	auto min = begin(in);
	auto i = next(min);
	while (i != end(in))
	{
		max = std::max(max, *i - *min);
		if (*i < *min) min = i;
		i++;
	}
	return max;
}

int main()
{
    int N; cin >> N;
    vector<int> v(N);
    copy_n(istream_iterator<int>(cin), N, begin(v));
    cout << find_max_diff(v);
}

And a similare one in Rust:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


fn solve(arr: Vec<u32>) -> u32 {
    let mut it = arr.into_iter();
    let mut min = it.next().unwrap();
    let mut max = 0;

    it.for_each(|x| {
        if x < min {
            min = x;
        } else {
            max = std::cmp::max(max, x - min);
        }
    });

    max
}

fn main() {
    use std::io::{BufRead};

    let numbers = std::io::stdin()
        .lock()
        .lines()
        .map(Result::unwrap)
        .skip(1)
        .next()
        .unwrap()
        .split(' ')
        .filter_map(|x| x.parse().ok())
        .collect();

    let output = solve(numbers);
    println!("{}", output);
}

The solution above hides two emerging patterns:

we calculate a running minimum (min is updated independently at every step)
we reduce to the max value on the difference between the current element and
the current running minimum

In Rust we can express it with scan (to calculate the running minimum) and max to reduce to the maximum value.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


fn solve(arr: Vec<i32>) -> i32 {
    arr.into_iter()
        .scan(std::i32::MAX, |min, x| {
            *min = std::cmp::min(*min, x);
            Some((*min, x))
        })
        .map(|(min, x)| x - min)
        .max()
        .unwrap()
}

In C++ we can express it using two functions of the standard library: partial_sum (where the sum operation is overriden by min) and inner_product, which accumulates inner products (where the multiply operation is overridden by minus) using the function max instead of sum.

1
2
3
4
5
6


vector<int> mins(v.size());
partial_sum(begin(v), end(v), begin(mins), [](auto l, auto r) { return min(l,r); });
cout << inner_product(begin(v), end(v), begin(mins), 0,
                      [](auto l, auto r){ return max(l, r); },
                      minus<>{}
                     );

From C++20, ranges’s view::partial_sum can help remove the support array:

1
2


auto mins = view::partial_sum(v, [](auto l, auto r){ return std::min(l, r); });
cout << ranges::max(view::zip_with(std::minus<>{}, v, rg));

It should be clear that mins is a lazy range and not a vector. The entire chain is lazy so the algorithm is one-pass.

The same concept can be expressed by Rust and iterators:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


fn main() {
    use std::io::BufRead;

    let output = std::io::stdin()
        .lock()
        .lines()
        .map(Result::unwrap)
        .skip(1)
        .next()
        .unwrap()
        .split(' ')
        .filter_map(|x| x.parse().ok())
        .scan(std::i32::MAX, |min, x| {
            *min = std::cmp::min(*min, x);
            Some((*min, x))
        })
        .map(|(min, x)| x - min)
        .max()
        .unwrap();

    println!("{}", output);
}

Haskell can be very terse when taking advantage of standard library higher order functions, like scanl1. The solution below is a complete program. It uses scanl1 (a particular form of scan where the first element is used as init) and zipWith to find differences.

1
2


solve xs = maximum $ zipWith (-) xs (scanl1 min xs)
main = interact $ show . solve . fmap read . words . last . lines

Another solution - less efficent and for some people preparatory for the previous solution - consists in using two prefix sums:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


int n; cin >> n;
vector<int> v(n);
copy_n(istream_iterator<int>(cin), n, begin(v));
vector<int> s_min(n);
partial_sum(begin(v), end(v), begin(s_min), [](auto... a){return min(a...);});
vector<int> s_max(n);
partial_sum(rbegin(v), rend(v), rbegin(s_max), [](auto... a){return max(a...);});

cout << inner_product(begin(s_max), end(s_max), begin(s_min), 0,
                     [](auto... a){ return max(a...); },
                     minus<>{});

Just for fun, an alternative solution is based on the Maximum Subarray Sum problem. We first calculate the differences between adjacent elements and then solve the maximum subarray problem on the resulting array.

In C++ we can combine several standard algorithms:

1
2
3
4
5
6
7
8


int n; cin >> n;
vector<int> v(n);
copy_n(istream_iterator<int>(cin), n, begin(v));
adjacent_difference(begin(v), end(v), begin(v));
partial_sum(next(begin(v)), end(v), begin(v), [](auto sum, auto i){
   return std::max(i, sum + i);
});
cout << *max_element(begin(v), prev(end(v)));