Leecode 最大子数组和

思路1：先了解前缀和的概念，  ，这题的答案可以转换为：将前缀和pre数组的下标作为x，下标对应的值作为y，建立坐标系得到一条pre折线，找到折现所有最小值与最大值差值最大的（最小值在前最大值在后）值就是本题的答案，也是与买卖股票最佳时机思路一样了

思路2：对于以nums[j]元素为结尾的最大字串和f(j) 只需要根据前一个元素的f（j-1）来推算，即Max(f(j-1)+nums[j], nums[j])，这样只需要遍历nums数组并使用pre数组记录以当前元素为结尾的最大子数组的和即可空间复杂度为O(n)时间复杂度为O(n)，因为只需要所有子数组的最大值，pre数组可以使用一个变量代替空间复杂度为O(1)，时间复杂度为O(n)

思路1代码如下：

    public static int maxSubArray(int[] nums){
        int currentMin =0; //记录截至到当前前缀和的最小值,初始值为pre[0] =0
        int currentPreSum = 0; //记录截至到当前元素的前缀和
        int max = Integer.MIN_VALUE; //记录所有当前前缀和与最小值的差值中最大的
        for (int num : nums) {
            currentPreSum+=num;
            max= Math.max(currentPreSum-currentMin,max);
            currentMin = Math.min(currentMin,currentPreSum);
        }
        return max;
    }

思路2代码如下：

    public static int maxSubArray(int[] nums) {
        int preMax = 0,max =nums[0];
        for (int num : nums) {
            preMax = Math.max(preMax+num,num);
            max = Math.max(max,preMax);
        }
        return max;
    }