Leetcode: Maximum Subarray (Dynamic programming)

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.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and 

conquer approach, which is more subtle.

Hide Tags

 Divide and Conquer Array Dynamic Programming

Show Similar Problems

1. Dynamic Programming ( O(log(n)) ):

Using max and temSum to save the previous results. 

////////////////////////

//codes

class Solution {

public:

       int maxSubArray(vector<int>& nums) {

              int sum = 0, max;

              if (nums.size() == 0)return max;

              max = INT_MIN;

              for (int i = 0; i<nums.size(); i++){

                     sum += nums[i];

                     //update the previous maximal value

                     if (sum>max)max = sum;

                     //discard the previous negtive sum

                     if (sum<0)sum = 0;

              }

              return max;

       }

};