Maximum Subarray

• Lintcode : 41 / Leetcode : 53
• Level : Easy

Problem

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

Example
Example1:

Input: [−2,2,−3,4,−1,2,1,−5,3]
Output: 6
Explanation: the contiguous subarray [4,−1,2,1] has the largest sum = 6.
Example2:

Input: [1,2,3,4]
Output: 10
Explanation: the contiguous subarray [1,2,3,4] has the largest sum = 10.
Challenge
Can you do it in time complexity O(n)?

Notice
The subarray should contain at least one number.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n)
space: O(n)

Answer

class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        // corner case
        if (nums.empty() || nums.size() == 0) return -1;
        int maxSum = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            nums[i] = max(nums[i], nums[i - 1] + nums[i]);
            maxSum = max(maxSum, nums[i]);
        }
        return maxSum;
    }
};

tags: DP

​