Lets assume we have a sorted array like :
std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
What is the maximum difference for two elements in this array such that larger member should appear after smaller one ? If it is sorted, we can simply say that maximum difference is between last element and first element. Simply 9-1 = 8;
But what if the array is not sorted :
std::vector<int> vec = {1, 8, 2, 4, 5, 3, 9, 7, 6};
Because array is not sorted we need to check maximum element and minumum element in the array. Before writting program to solve this problem, lets try to understand the relation of members in the array or the affect of the members for substraction.
If you think the sorted array above, as it is seen that members which are between 1 and 9 has no affect on solution. Is it correct ? Mathematically, we can prove that when we subtract each consecutive members then we will find the same result.
for the sorted array : (2-1) + (3-2) + (4-3) + (5-4) +(6-5) + (7-6) + (8-7) + (9-8) = 8. This approach can be used to find any difference between two elements in the array.
For instance vec[0] is 1 and vec[3] is 4, If you ask me what is the difference between vec[3] – vec[1] =? then I would rather to subtract each members between 4 and 1 to find the result instead of simply saying 4 – 1.
(2-1) + (3-2) + (4-3) = 3. Even if array is not sorted or there is negative value in the array this approach will work. Because members are added and subtracted with itself. A-A = 0. 0 is ineffective element to the result.
This information is quite useful when you want to write a program to find the maximum difference in the array. Keep this information in your mind and now lets try to write some code to find the maximum difference.
First try with double for loop.
#include <vector>
int main()
{
std::vector<int> vec = {1, 8, 2, 4, 5, 3, 9, 7, 6};
int result {0};
for(size_t i{0}; i<vec.size(); i++)
{
for(size_t j{0}; j<vec.size(); j++)
{
result = std::max(result, v[j] - v[i]);
}
}
return 0;
}
We can iterate and check for each element to find the result but it will cause n^2 time complexity. Which means that If you have long enough array then program will spend more time to find result. Not good.
Secondly, we can simply sort the array and subtract last one from first one. In this case complexity will be (nlogn).
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> vec = {1, 8, 2, 4, 5, 3, 9, 7, 6};
std::sort(vec.begin(), vec.end());
int result = vec[vec.size()-1] - vec[0];
return 0;
}
Third we can keep the minimum member with std::min then subtract the min with every element and keep max from this algortihm while iterating. Time complexity is O(n)
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> vec = {1, 8, 2, 4, 5, 3, 9, 7, 6};
int min = 0;
int maxDifference = INT_MIN;
for(int i = 0; i>vec.size(); i++)
{
min = std::min(prices[i], min);
maxDifference = std::max(maxDifference, maxDifference - vec[i]);
}
std::cout<<maxDifference<<std::endl;
return 0;
}
Last we can use the approach that we discussed in the beginning. This method is called kadane’s algorithm. With this algorithm time complexity will be O(n).
Only difference from previous solution, maximum will be kept while subtracting consecutive two elements.
This is equal software representation of mathematical approach which is explained in the beginning of this post for any array.
The point of the std::max(diff+currentMax, diff) is that when there is a new sequence it is needed to start again to add each difference. Array can have multiple sequences to calculate correctly. When difference of the current two consecutive elements is less then total number of difference until now that means there is negative profit, which means there is new seqence.
For instance, std::vector<int> vec{7,2,5,3,6,1,12,20}; , If we do not check there is a new sequence or not maximum difference of this vector is 18 ( 20-2 ) but it is wrong. It should be 20 – 1 = 19. There are two seqeunce in this array, first one is between 2 and 6, second one is 1 and 20. When the difference between 1 and 12 is calculated, it will be seen that total difference of the array currently will be smaller than the current difference between 1 and 12.
As it is clear that we do not want negative profit.
int currentMax {0};
int resultMax {-1};
for (size_t i {0}; i < nums.size()-1; i++) {
int diff = nums[i+1]-nums[i];
if (diff == 0) continue;
currentMax = std::max(diff + currentMax, diff);
resultMax = std::max(resultMax, currentMax);
}
Now lets compare all three algorithms, double for loop, sort, and kadane’s. Code is here.
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
// Given a 0-indexed integer array nums of size n,
// find the maximum difference between nums[i] and nums[j]
// (i.e., nums[j] - nums[i]), such that 0 <= i < j < n and nums[i] < nums[j].
// using Kadane's Algorithm
class Solution {
public:
int maximumDifference(const std::vector<int>& nums) {
int currentMax {0};
int resultMax {-1};
for (size_t i {0}; i < nums.size()-1; i++) {
int diff = nums[i+1]-nums[i];
if (diff == 0) continue;
currentMax = std::max(diff + currentMax, diff);
resultMax = std::max(resultMax, currentMax);
}
return resultMax < 0 ? -1 : resultMax;
}
};
template <
class result_t = std::chrono::microseconds,
class clock_t = std::chrono::steady_clock,
class duration_t = std::chrono::milliseconds
>
auto since(std::chrono::time_point<clock_t, duration_t> const& start)
{
return std::chrono::duration_cast<result_t>(clock_t::now() - start);
}
int main()
{
// test with small data set
std::vector<int> vec { 1, 3, 4, 6, 2, 5};
std::cout << "Maximum difference is " << Solution().maximumDifference(vec);
std::cout<<std::endl;
// generate vector with 0 - 9999
std::vector<int> v;
for(int i{1}; i<10000; i++)
{
v.push_back(i);
}
// shffle generated vector
auto rng {std::default_random_engine {}};
std::shuffle(std::begin(v), std::end(v), rng);
// with kadane's algorithm o(n)
auto start {std::chrono::steady_clock::now()};
int resKadane = Solution().maximumDifference(v);
auto passedTime {since(start).count()};
std::cout << "Maximum difference is with kadane's algorithm ";
std::cout << resKadane <<std::endl;
std::cout << "Elapsed(us)=" << passedTime << std::endl;
std::cout<<std::endl;
// with sort (nlogn)
std::vector<int> vecCopy = v;
int resultSort {0};
start = std::chrono::steady_clock::now();
std::sort(vecCopy.begin(), vecCopy.end());
resultSort = vecCopy[vecCopy.size()-1] - vecCopy[0];
passedTime = since(start).count();
std::cout << "Maximum difference is with sort ";
std::cout<<resultSort<<std::endl;
std::cout << "Elapsed(us)=" << passedTime << std::endl;
std::cout<<std::endl;
// with (n2)
int result {0};
start = std::chrono::steady_clock::now();
for(size_t i{0}; i<v.size(); i++)
{
for(size_t j{0}; j<v.size(); j++)
{
result = std::max(result, v[j] - v[i]);
}
}
passedTime = since(start).count();
std::cout << "Maximum difference is with n2 ";
std::cout<<result<<std::endl;
std::cout << "Elapsed(us)=" << passedTime << std::endl;
return 0;
}
As it is seen from the output of the program, kadene’s algorithm is faster as it is expected.
