Maximum Subarray

Maximum Subarray

Description:

Given an array of integers, find a contiguous subarray which has the largest sum.

Notice:

The subarray should contain at least one number.

Example:

Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

分析：

参考：

wikipedia

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:    
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    int maxSubArray(vector<int> nums) {
        // write your code here
        int max_endding_here = nums[0];
        int max_so_far = nums[0];
        
        for (int i = 1;i < nums.size();i++) {
            max_endding_here = max(max_endding_here + nums[i], nums[i]);
            max_so_far = max(max_so_far, max_endding_here);
        }
        return max_so_far;
    }
};