Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.
Dynamic Programming Algorithm to Compute the Maximum Sublist Sum
If we use f(n) to store the maximum sum that ends at the n-th number in the array, then we have the following Dynamic Programming (DP) recurrence formula:
1 2 | f(0) = num[0] f(n) = max(f(n-1) + num[n], num[n]) |
f(0) = num[0] f(n) = max(f(n-1) + num[n], num[n])
So the answer would be the maximum value of f(0) to f(n-1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); vector<int> f(n, INT_MIN); f[0] = nums[0]; int sum = f[0]; for (int i = 1; i < n; i ++) { f[i] = max(f[i - 1] + nums[i], nums[i]); sum = max(sum, f[i]); } return sum; } }; |
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> f(n, INT_MIN);
f[0] = nums[0];
int sum = f[0];
for (int i = 1; i < n; i ++) {
f[i] = max(f[i - 1] + nums[i], nums[i]);
sum = max(sum, f[i]);
}
return sum;
}
};The time complexity is O(n) and the space complexity is O(n). As each iteration, the DP formula depends on its previous value, so the space can be optimised to O(1).
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); int prev = nums[0]; int sum = prev; for (int i = 1; i < n; i ++) { prev = max(prev + nums[i], nums[i]); sum = max(sum, prev); } return sum; } }; |
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int prev = nums[0];
int sum = prev;
for (int i = 1; i < n; i ++) {
prev = max(prev + nums[i], nums[i]);
sum = max(sum, prev);
}
return sum;
}
};This Dynamic Programming Algorithm is also known as Kadane’s Algorithm.
Greedy Algorithm
We keep a variable to store the current sum. If the sum is below zero, then we reset it to the current number (start from current number). The implementation is quite similar to above DP but slightly different.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution { public: int maxSubArray(vector<int>& nums) { int sum = 0; int curmax = INT_MIN; for (int i = 0; i < nums.size(); i ++) { if (sum >= 0) { sum += nums[i]; } else { sum = nums[i]; } curmax = max(sum, curmax); } return curmax; } }; |
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0;
int curmax = INT_MIN;
for (int i = 0; i < nums.size(); i ++) {
if (sum >= 0) {
sum += nums[i];
} else {
sum = nums[i];
}
curmax = max(sum, curmax);
}
return curmax;
}
};Similar to DP, this approach is O(n) time with O(1) space.
Maximum Subarray Sum Algorithms
- Teaching Kids Programming – Maximum Subarray by Dynamic Programming and Greedy Algorithm
- Compute the Maximum Subarray via Dynamic Programming or Greedy Algorithms
- Teaching Kids Programming – Max Subarray Sum by Kadane’s Algorithm
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: C/C++ Coding Exercise - Find the Duplicate Number
Next Post: C++ Coding Exercise - Sort Colors (Bucket Sort and Dutch Flag)
