leetcode题解 problem53 Maximum Subarray

Tags:

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.

1 class Solution {
2 public:
3   int maxSubArray(vector<int>& nums) {
4         
5     }
6 };

题意:

求子串和最大值

题解:

经典动态规划题目。

列下状态转移方程:

设数组为T(i), 设S(i)是数组从0到i位置的后缀子串和的最大值。明确一下,S(i)对应的子串的左右2个索引[start,end],start的取值范围是[0,i],end必然是i,即[start,end]是数组[0,i]段的一个后缀。换句话说,S(i)不代表前n个数据中最大子串和,只代表与第n个数组合时,所能得到的最大值。

可得:

S(i) = T(i) + ( S(i - 1) > 0 ? S(i - 1) : 0 )

方程的含义是: 求S(i)时,S(i-1)如果大于0,那么说明i-1存在一个后缀(必然是连续的)使得S(i-1)大于0,此时把T[i]也加进去S(i-1),当然就是S(i)的最长后缀了。(S(i)可能小于等于0);

S(i-1)如果小于等于0,说明S(i-1)对增大S(i)没有意义了,也即说明S(i)的最长后缀等于[i,i],S(i) = T(i)。

空间复杂度O(n),时间复杂度O(n)。

代码:

 1   int maxSubArray(vector<int>& nums) {
 2      if (nums.size() == 0)
 3          return 0;
 4      if (nums.size() == 1)
 5          return nums[0];
 6      vector<int> s(nums.size() + 1);
 7      s[0] = 0;
 8      int maxS = INT_MIN;
 9      for (int i = 1; i <= nums.size(); ++i){
10          s[i] = nums[i - 1] + (s[i - 1] > 0 ? s[i - 1] : 0);
11          if (s[i] > maxS){
12              maxS = s[i];
13          }
14      }
15      return maxS;
16  }

考虑到S(i)数组对于这个题目是多余的,题目只是要求S(i)的max值,那么可以改下代码,把空间复杂度从O(n)降到O(1)。

 1   int maxSubArray(vector<int>& nums) {
 2      if (nums.size() == 0)
 3          return 0;
 4      if (nums.size() == 1)
 5          return nums[0];
 6      int sum = 0, maxS=INT_MIN;
 7      for (int i = 1; i <= nums.size(); ++i){
 8          sum = nums[i - 1] + sum;
 9          if (sum < 0)
10              sum = 0;
11          if (sum > maxS){
12              maxS = sum;
13          }
14      }
15      return maxS;
16  }
(未经授权禁止转载)
Written on June 26, 2015

博主将十分感谢对本文章的任意金额的打赏^_^