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 subarray and subsequence and print them.
Constraints:
 1 <= N <= 10^5
 10^4 <= ai <= 10^4
Solution
As for the maximal sum of a subarray (each numbers are consecutive), the DP equation should be dp[i] = max(dp[i1]+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 subsequence, the DP equation should be dp[i] = max(dp[i1]+ai, max(ai, dp[i1])) and the dp[i] means the maximal sum of the subsequence till index i which might not include the current number.


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