题解 | #连续子数组的最大和#
连续子数组的最大和
https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484
首先看到最大和，然后观察是求上面的最大值，一看连续子数组
这时候脑子里面应该会有很多idea
首先，既然是连续的子数组那如果都是正数的话，
因为数组中有正有负有0，因此每次遇到一个数，要不要将其加入我们所求的连续子数组里面，是个问题，有可能加入了会更大，有可能加入了会更小，而且我们要求连续的最大值，因此这类有状态转移的问题可以考虑动态规划。
从数组的开头往下走，sum记录连续的和，max记录最大值
sum和max的初始值为数组第一个元素array[0]
数组不断往下走，不断更新max的值。如果当sum<array[0]时，此时就需要丢弃之前统计的，所以令sum=0
import java.util.*;
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
//记录到下标i为止的最大连续子数组和
int[] dp = new int[array.length];
dp[0] = array[0];
int maxsum = dp[0];
for(int i = 1; i < array.length; i++){
//状态转移：连续子数组和最大值
dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
//维护最大值
maxsum = Math.max(maxsum, dp[i]);
}
return maxsum;
}
}
查看41道真题和解析