max_diff.cpp

#include <iostream>
#include <vector>
using namespace std;

int maxDiff(std::vector<int> & nums)
{
    if (nums.size() <= 1)
        return 0;
    vector<int> max_v;

    max_v.push_back(nums[0]);

    for (size_t i = 1; i < nums.size(); ++i)
    {
        max_v.push_back(max(max_v.back(), nums[i]));
    }

    int min_v = nums[nums.size() - 1];
    int res = max_v[nums.size() - 2] - min_v;
    for (int i = nums.size() - 2; i - 1 >= 0; --i)
    {
        min_v = min(min_v, nums[i]);
        res = max(res, max_v[i - 1] - min_v);
    }

    return res;
}

int main()
{
    vector<int> a = {1, 2, 4, 1, 1, 1, 0, 2};
    vector<int> b = {1, 1, 1, 1, 1, 1};
    cout << maxDiff(a) << endl;
    cout << maxDiff(b) << endl;
}