leetcode 53. Maximum Subarray 子数组最大和

问题：给定一个数组，其中当然有很多的子数组，在所有子数组中，找到相加和最大的一组，最后返回累加和。

要求： 时间复杂度达到 O(N)

分析：这道题我们最容易想到的解法就是遍历数组，以每个元素作为子数组的首元素进行一次遍历，找出以该元素为首的子数组的累加和，找出其中最大的。需要进行(N+1)*N/2，时间复杂度为O(N*N)级别。如何能够使时间复杂度达到O(N)级别呢？下面开始我们的解法。

解法：首先设置两个变量cur（用来记录遍历过的位置元素的累加和），max（保存子数组累和和的最大值）。遍历过程：初始时cur=0，从左向右开始遍历，cur累加当前元素，若cur<0，我们将cur置为0；若cur>max，我们更新当前max为cur的值；继续遍历直到最后一个位置。由于我们只遍历了一次，时间复杂度为O(N)。那么为什么我们这么做可以得到正确结果呢？假设当前子数组的最大和存在，那么，这个子数组的任意前缀（就是数组前几个元素）的累加和都不可能小于零，如果小于零了，这部分只会使整个子数组的累加和变小。所以当cur<0是，我们让cur=0。如果整个数组里面的值都是负数，max会记录最大的那一个。

public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int cur = 0; int max = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { cur += nums[i]; max = Math.max(cur, max); if (cur < 0) { cur = 0; } } return max; }