mediumArraysDynamic ProgrammingKadane's Algorithm

Maximum Subarray

Est. Time: 20 minTime: O(n)Space: O(1)

Description

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

Examples

Example 1 Input:nums = [-2,1,-3,4,-1,2,1,-5,4]

Output:6

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

Example 2 Input:nums = [1]

Output:1

Constraints

▪1 <= nums.length <= 10^5
▪-10^4 <= nums[i] <= 10^4

Hints

Hint 1Show

Brute force: check all subarrays — O(n²).

Hint 2Show

Can you solve it in one pass?

Hint 3Show

Kadane's Algorithm: track the current subarray sum. If it goes negative, reset to 0.

Starter Code

Solution.cpp

1class Solution {
2public:
3    int maxSubArray(std::vector<int>& nums) {
4        // Your code here
5        return 0;
6    }
7};

Solution

Solve the problem first before reviewing the solution!

Up Next

Climbing Stairs

Back to C++ Problems