0%

53. Maximum Subarray

发表于 更新于 分类于 阅读次数：
本文字数： 829 阅读时长 ≈ 1 分钟

2018年5月2日 下午3:54
Maximum Subarray - LeetCode

  1. 这道题可以说是的升级版
  2. 这次遍历的对象是01 02….0~(n-1),但是加上一个条件：最右边的单个元素的一定要！
  3. 直接0~(n-1)不对的原因是：找不到前后的关系
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    //这次遍历的对象是0~1 0~2....0~(n-1),但是加上一个条件：最右边的单个元素的一定要！
    //也就是说，这回的dp表示的是：包含最后一个元素的最大值。有可能不包含最后一个时的值更大，所以需要我们再加一步：和max比较大小
    //这道题这么绕一下，不向上一题一样，直接一个递推式子就完成了的原因是：在这道题中找不大合适的递推公式
    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        if(nums.size() == 1) return nums[0];
        std::vector<int> dp(nums.size()+1, 0);
        
        dp[0] = nums[0];
        dp[1] = nums[1]+nums[0] > nums[1] ? nums[1]+nums[0] : nums[1];
        
        int max = dp[0] > dp[1] ? dp[0]: dp[1];
        for(int i = 2; i < nums.size(); i++){
            // 这里的if-else就是递推式子
            if(dp[i-1] > 0){
                dp[i] = dp[i-1] + nums[i];
                
            }
            else{
                dp[i] = nums[i];
            }
            
            if(max < dp[i]) max = dp[i];
            // printf("%d- ",dp[i]);
        }
       
        return max;
    } 
};