53. Maximum Subarray

• Difficulty: Easy

• Topics: Array, Divide and Conquer, Dynamic Programming

• Similar Questions:

  • Best Time to Buy and Sell Stock

  • Maximum Product Subarray

  • Degree of an Array

  • Longest Turbulent Subarray

Problem:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solutions:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int suffix = 0;
        int ret = INT_MIN;
        int sum = 0;

        for (auto num : nums) {
            sum += num;
            ret = max(ret, sum - suffix);
            suffix = min(suffix, sum);
        }

        return ret;
    }
};