未在上面列出的题目 - Maximum Subarray[M]

053. Maximum Subarray[M]

题目

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array[-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

即求一个整数数组中的和最大的连续子数组问题

思路

首先，这个问题可以用枚举来求，比较容易想到 i (0 … n-1), j (0 .. n-1)，然后每次求和的时候，用个巧办法，不用再次循环：

• j 移动的时候把当前j所在的值加到和上
• i 移动的时候把i之前的值减去。
  时间复杂度O(N^2)

public class Solution {
    public int maxSubArray(int[] nums) {
        int sum ,maxsum;
        maxsum = nums[0];
        for(int i = 0;i < nums.length;i++)
        {
            sum = 0;
            for(int j = i;j < nums.length;j++)
            {
                sum += nums[j];
                maxsum = sum>maxsum?sum:maxsum;
            }
        }
        return maxsum;
    }
}

D&C

之前的枚举的算法可以，但是时间复杂度太高会超时，于是继续优化。有人提出了D&C算法
把数组分成差不多相等的两部分，最长数组要不在左边，要不在右边，要不在中间。
分好分，就是2分，关键是怎么合。
合的话就是左边的最大值和右边的最大值比较，然后再跟合起来后中间的最大值比较。
中间的最大值求法O(n)：

• 左边的最大值不断+右边的值
• 右边最大值不断+左边的值