连续子数组的最大和

    public int FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int max=array[0];
        for(int i=1;i<array.length;i++){
            array[i]=Math.max(array[i] ,array[i]+array[i-1]);
            max=Math.max(array[i] ,max);
        }
        return max;
    }

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型一维数组
     * @return int整型
     */
    public int FindGreatestSumOfSubArray (int[] array) {
        // write code here
        // 方法一：空间复杂度O(n)
        // dp[i]表示以num[i]结尾的数组最大和
        // int[] dp = new int[array.length];
        // dp[0] = array[0];
        // int max = array[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 = dp[i] > max ? dp[i] : max;
        // }
        // return max;

        // 方法二：空间复杂度O(1)
        // 记录子数组和
        int sum = array[0];
        // 记录最大子数组和
        int res = array[0];
        for (int i = 1; i < array.length; i++) {
            // 原子数组和为正，则原子数组与当前元素组成的子数组和大于以当前元素
            // 单独构成的子数组
            if (sum > 0) sum = sum + array[i];
            // 原子数组和不为正，则原子数组与当前元素组成的子数组和小于以当前元素
            // 单独构成的子数组，则以当前元素作为新的最大子数组
            else sum = array[i];
            // 记录最大值
            res = sum > res ? sum : res;
        }
        return res;
    }
}

 public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==1){
            return array[0];
        }
        int[] dp=new int[array.length];
        dp[0]=array[0];
        int ans=array[0];
        for(int i=1;i<array.length;i++){
            dp[i]=Math.max(dp[i-1]+array[i],array[i]);
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }

// 递归 + dp优化 = 动态规划
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = -1;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            int maxSum = getMaxSum(array, i, dp);
            dp[i] = maxSum;
            if (maxSum > max) max = maxSum;
        }
        return max;
    }

    private int getMaxSum(int[] array, int cur, int[] dp) {
        if (cur == 0) {
            return array[0];
        }
        return Math.max(dp[cur - 1] + array[cur], array[cur]);
    }
}

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int len = array.length, i = 0, sum = 0, max = array[0];
        for (i = 0; i < len; i++) {
            sum = Math.max(sum + array[i], array[i]);
            max = Math.max(max, sum);
        }
        return max;
    }
}

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int pre = array[0], ans = array[0];
        for (int i = 1; i < array.length; i++) {
            pre = pre > 0 ? pre + array[i] : array[i];
            ans = Math.max(ans, pre);
        }
        return ans;
    }
}

public class Solution {
    /**
     * 时间复杂度O(n) 空间复杂度O(n)
     * 假设数组: 1,-2,3,10,-4,7,2,-5
     * 每次找到以 i 结尾的最大子数组之和
     * n[0] = 1
     * n[1] = Max(-2, (-2 + n[0]->1)) = -1
     * n[2] = Max(3, (3 + n[1]->-1 )) = 3
     * n[3] = Max(10, (10 + n[2]->3 )) = 13
     * n[4] = Max(-4, (-4 + n[3]->13 )) = 9
     * n[5] = Max(7, (7 + n[4]->9 )) = 16
     * n[6] = Max(2, (2 + n[5]->16 )) = 18
     * n[7] = Max(-5, (-5 + n[6]->18 )) = 13
     * 由此得知，最大子数组之和为18
     * *****************************************************
     * 时间复杂度O(n) 空间复杂度O(1)
     * 数组从下标1开始遍历，因为以下标0结尾的最大子数字之和，只有它自己，所以为固定值
     * 每次遍历，都是求最大值 Max(当前元素+前驱元素的子数组之和 , 当前元素) ，即为当前元素的子数组最大和
     * 所以可以取消dp数组， 采用一个max记录最大子数组之和，一个pre记录前驱元素的子数组之和即可
     * 解法如下：
     */
    public int FindGreatestSumOfSubArray(int[] array) {

        // 记录数组最大值，初始值为第一个元素
        int max = array[0];
        // pre用于记录循环中 i索引位置的前一位数字的最大子数组之和
        // 初始值为第一个元素
        int pre = array[0];

        // 从第二个元素开始遍历，每次循环，求最大值 Max(当前元素+前置元素的子数组之和 , 当前元素) ，即为当前元素的子数组最大和
        // 即每次循环都在找以i结尾的数组元素，子数组最大之和
        for (int i = 1; i < array.length; i++) {
            // 将计算出来的当前元素子数组最大和，赋予pre，下次循环时即为 i的前置元素最大和
            pre = Math.max(array[i] + pre, array[i]);
            // 当前元素计算出以i结尾的子数组最大之和后，与max相比取最大值，再重新赋予max
            max = Math.max(max, pre);
        }

        // 循环结束max即为解
        return max;
    }
}

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array.length == 0 || array == null) {
            return 0;
        }
        int temp = 0;
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (temp <= 0) {
                temp = array[i];
                if (temp > max) {
                    max = temp;
                }
            } else {
                temp += array[i];
                if (temp > max) {
                    max = temp;
                }
            }

        }

        return max;
    }
}

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
       //默认第一个为最大
        int max = array[0];
        //array[i]以array结尾的最大子数组和
        for (int i = 1; i < array.length; i++) {
            //前一个子数组的和是否对于当前子数组有增量？
            //有的话加上前一个子数字的和
            //没有的话加0
            array[i]+= Math.max(array[i - 1], 0);
            //同时找最大值
            max = Math.max(max, array[i]);
        }
        return max;
    }
}

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0];
        int[] dp = new int[array.length];
        dp[0] = array[0];
        
        for (int i = 1; i < array.length; i++) {
            dp[i] = Math.max(array[i], dp[i - 1] + array[i]);
            if (dp[i] > max) max = dp[i];
        }
        
        return max;
    }
}

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            array[i] = Math.max(array[i-1] + array[i], array[i]);
            if (max < array[i]) {
                max = array[i];
            }
        }
        return max;
    }
}