连续子数组的最大和

题目

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

题解

思路1

动态规划（/递归）

递归函数：

F（n） = nums[i] i =0 或 F(n-1) < 0

F(n) = num[i] + F(n-1) i ≠0 或 F(n-1) >= 0

按照上述函数写法：

时间复杂度: O(N ^ 2)- 空间复杂度: O(1)

public int FindGreatestSumOfSubArray(int[] array) {
   int max = Integer.MIN_VALUE;
   for (int i = 0;i< array.length ; i++){
           int tmp = FindGreatestSumOfSubArray(array,i);
        if (max < tmp)
            max = tmp;
      }
     return max;
}

public int FindGreatestSumOfSubArray(int[] array,int idx) {
    if (idx == 0)
        return array[0];

    int pre = FindGreatestSumOfSubArray(array,idx - 1);
    if (pre <= 0)
        return array[idx];
    else return pre + array[idx];
}

改成迭代，优化一下：

时间复杂度: O(N)- 空间复杂度: O(N)

public int FindGreatestSumOfSubArray(int[] array) {
    if (array.length == 0)
        return 0;

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

思路2

核心思想：当加上一个正数时，和会增加；当加上一个负数时，和会减少。所以在数组遍历的过程中，一边累加数组元素，一边比较累加结果和0的关系，如果累加结果是负数，则应当把累加结果抛弃，并将累加结果清零。

时间复杂度: O(N)- 空间复杂度: O(1)

public int maxSubArray(int[] nums) {
    if (nums.length == 0)
        return 0;

    int subSum = 0;
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        if (subSum <= 0)
            subSum = nums[i];
        else subSum += nums[i];

        if (subSum > maxSum)
            maxSum = subSum;
    }
    return maxSum;
}