JZ30 连续子数组的最大和

• 思路：动态规划
• 时间：2021年8月18号

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        //动态规划处理
        /* int[] dp = new int[array.length + 1];
        dp[0] = 0;
        int ret = array[0];

        for (int i = 1; i <= array.length; i++) {
            dp[i] = Math.max(dp[i-1] + array[i-1], array[i-1]);

            ret = Math.max(ret, dp[i]);
        }

        return ret; */
        int ans = 0;
        if (array.length < 1)
            return ans;

        int ret = array[0];
        int tem = 0;
        int max = ret;

        for (int num : array) {
            if (tem + num < 0) {
                tem = 0;
            } else {
                tem = tem + num;
            }

            ret = Math.max(tem, ret);
            max = Math.max(num, max);
        }
        if (ret != 0) {
            return ret;
        }
        return max;
    }
}