1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_sum  = INT_MIN; 
        int max_pre  = 0; 
        int max_cur = 0; 
        
         for (int i = 0; i  < nums.size(); i++){
             int cur_item = nums[i]; 
             if(max_pre  > 0 ){
                 max_cur = max_pre + cur_item;
             }else {
                 max_cur  = cur_item; 
             }
             
             max_sum = max(max_sum, max_cur);
             max_pre = max_cur; 
         }
        
        return  max_sum; 
    }
};

 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
32
33
34
35
36
37
38
39
40
41
42
43

#include <iostream>
using namespace std;


int max_subarr_sum(int arr[], int n)
{
    // 最大值
    int max_sum = INT_MIN;

    // 前一个位置最大值 
    int max_pre = 0;
    
    // 当前位置最大值 
    int max_cur = 0;
    
    // 遍历
    for (int i = 0; i < n; i++)
    {
        int cur_item  = arr[i];
        if (max_pre > 0) {
            max_cur = max_pre + cur_item;
        } else {
            max_cur = cur_item; 
        }

        max_sum  = max(max_sum, max_cur);
        max_pre = max_cur;

    }

    return max_sum;
}

int main()
{
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "The sum of contiguous sub-array with the largest sum is " <<
            max_subarr_sum(arr, n);

    return 0;
}