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.
- 1 <= N <= 10^5
- -10^4 <= ai <= 10^4
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.
Always welcome new ideas and
practical tricks, just leave them in the comments!