Maximal Sum of Subarray and Subsequence

Maximal Sum of Subarray and Subsequence

Given an array a1, a2, …, an of N elements, you are required to find out the maximal sum of the sub-array and sub-sequence and print them.

Constraints:

  • 1 <= N <= 10^5
  • -10^4 <= ai <= 10^4

test

Solution

As for the maximal sum of a sub-array (each numbers are consecutive), the DP equation should be dp[i] = max(dp[i-1]+ai, ai) to keep it contiguous while the dp[i] is the maximal consecutive sum till index i which will always include the current number ai; but when it comes to the sub-sequence, the DP equation should be dp[i] = max(dp[i-1]+ai, max(ai, dp[i-1])) and the dp[i] means the maximal sum of the sub-sequence till index i which might not include the current number.

1
2
3
4
5
6
7
8
9
void traverse(const vector<int>& arr, int& cMax, int& nMax){
vector<int> cArr(arr.size());
cMax = cArr[0] = arr[0], nMax = arr[0];
for(int i = 1; i < arr.size(); ++i){
cArr[i] = max(cArr[i-1]+arr[i], arr[i]); //the maximal ending with i;
cMax = max(cArr[i], cMax); //we have to select here;
nMax = max(nMax+arr[i], max(arr[i], nMax)); //the maximal till i;
}
}

Always welcome new ideas and practical tricks, just leave them in the comments!