题解 | #连续子数组的最大和#

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        // 分析题目，跟全局有关，并且不是可以递推的关系，用贪心算法来解决
        // 并且这个题目很典型，求子数组的和的最大值，就是卡登算法
        // dp[i] 表示以i结尾的连续子数组最大和
        // dp[i-1] > 0   dp[i] = dp[i-1] + array[i]
        // dp[i-1] <= 0  dp[i] = array[i]
        int [] dp = new int [array.length];
        dp[0] = array[0];
        int max = dp[0];
        for(int i =1;i < array.length;i++) {
            if(dp[i-1] > 0){
                dp[i] = dp[i-1] + array[i];
            }else{
                dp[i] = array[i];
            }
            max = Math.max(max,dp[i]);
        }
        return max;

        
    }
}

这个题目是动态规划里面很典型的题目，用卡登算法解决。

dp[i] 表示的是尾部以i结尾的子数组的最大值，也就是说，必须是包含array[i]的，如果前面的大于0，就把他们加上，否则，array[i]作为头部。

然后再在dp数组里面找到最大值即可。