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)
  1. public class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int sum ,maxsum;
  4.         maxsum = nums[0];
  5.         for(int i = 0;i < nums.length;i++)
  6.         {
  7.             sum = 0;
  8.             for(int j = i;j < nums.length;j++)
  9.             {
  10.                 sum += nums[j];
  11.                 maxsum = sum>maxsum?sum:maxsum;
  12.             }
  13.         }
  14.         return maxsum;
  15.     }
  16. }

D&C

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

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