Link to Question

EASY

Maximum Subarray

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:

nums = [-2,1,-3,4,-1,2,1,-5,4]

Output:

6

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

---

Constraints

• 1 ≤ nums.length ≤ 10⁵
• -10⁴ ≤ nums[i] ≤ 10⁴

---

Solution: Kadane's Algorithm

• Time Complexity: O(n)
• Space Complexity: O(1)

C++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int cur = 0, ans = INT_MIN;
        for (auto c : nums) {
            cur += c;
            ans = max(ans, cur);
            if (cur < 0)  cur = 0;
        }
        return ans;
    }
};