lc53-Maximum Subarray

發表於   |   分類於   |   0 comments   |   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int l = nums.size();
        vector<int> dp(l, 0);
        dp[0] = nums[0];
        for (int i = 1; i < l; i++) {
            if (dp[i - 1] < 0)
                dp[i] = nums[i];
            else 
                dp[i] = nums[i] + dp[i - 1];
        }
        int max = INT_MIN;
        for (int i = 0; i < l; i++) {
            if (dp[i] > max)
                max = dp[i];
        }
        return max;
    }
};

updated Dec 23, 2016:

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