Click here to return to the General Catalog
[Title]
[Method 1]
Find the segment that sums to the largest nums[a] + ... +nums[b] is largest, i.e. sum[b] - sum[a-1] is largest.
Let's start by finding the sum array. sum[i] is the sum of the first i terms.
Original array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Cumulative sum: [-2, -1, -4, 0, -1, 1, 2, -3, 1]
Now the problem is to find a number i in front and a number j behind such that the difference between the two numbers sum[j]-sum[i] is maximized. This is similar to question 121, find the maximum return on a stock, find a value to buy in front, find a value to sell behind, and then find the maximum return.
But here's where it's a little different, that is, if it's all positive numbers, like 3,2,4,8,1. the best result is 8, not 8-2=6. So, if the number before it is positive, subtracting a positive number will make it smaller, so it's better to leave it out. Only if the previous number is negative, subtracting a negative number will make it bigger. Therefore, you can set min=0 for the initial test.
dp Eq:
Maximum of first i items = max{maximum of first i-1 items, sum[i]-min}
Code:
Results:
[Method 2]
dp[i] denotes the maximum sum of consecutive subarrays ending with the ith element.
Maximum sum ending with the ith element = max{only one of its own elements nums[i], maximum sum ending with i-1th + nums[i]}. Thus:
if(dp[i-1]<0){
dp[i] = nums[i];
}else{
dp[i] = dp[i-1]+nums[i];
}
Examples:
Original array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
dp[0] ：[-2, ] //dp[0]=-2
dp[1] : [-2, 1 ] // Since dp[0] = -2, the largest sum ending in 1 is better than not adding the preceding negative number.
dp[2] : [-2, 1, -2 ] //dp[1] = 1, so dp[2] = 1+nums[2]
dp[3] ：[-2, 1, -2, 4 ]
dp[4] ：[-2, 1, -2, 4, 3 ]
dp[5] ：[-2, 1, -2, 4, 3, 5 ]
dp[6] ：[-2, 1, -2, 4, 3, 5, 6 ]
dp[7] ：[-2, 1, -2, 4, 3, 5, 6, 1 ]
dp[8] ：[-2, 1, -2, 4, 3, 5, 6, 1, 5 ]
The result is dp[6]=6.
Code:
Results:
