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

// 动态规划问题，dp[i]数组是动态规划数组，遇到负数就保留为原数组值
// dp[i] = Math.max(arr[i],arr[i]+dp[i-1])这个式子妙啊///
// max的初始值最好保存为原数组首个元素
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型
     */
    public int FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int max = array[0];
        for(int i=1;i<array.length;i++){
            dp[i] = Math.max(array[i],array[i]+dp[i-1]);
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}