53. Maximum Subarray

Question

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

A subarray is a contiguous part of an array.

Example 1:

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

Tracking:

At nums[0] => -2
local_max = max(-2, 0 + -2 = -2) = -2, global_max = -2

At nums[1] => 1
local_max = max(1, -2 + 1 = -1) = 1, global_max = 1

At nums[2] => -3
local_max = max(-3, 1 + -3 = -2) = -2, global_max = 1

***** Start of contiguous sub array *****
This is where the global_max increases

At nums[3] => 4
local_max = max(4, -2 + 4 = 2) = 4, global_max = 4

At nums[4] => -1
local_max = max(-1, 4 + -1 = 3) = 3, global_max = 4

At nums[5] => 2
local_max = max(2, 3 + 2 = 5) = 5, global_max = 5

At nums[6] => 1
local_max = max(1, 5 + 1 = 6) = 6, global_max = 6

***** End of contiguous sub array *****
This is where the local_max decreases

At nums[7] => -5
local_max = max(-5, 6 + -5 = 1) = 1, global_max = 6

At nums[8] => 4
local_max = max(4, 1 + 4 = 5) = 5, global_max = 6

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104

---

Approach

1. Using Kadane’s Algorithm - Nice article here Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work?
2. While iterating through the array, calculate the current max and save as local_max.
3. After which, update the maximum global_max when local_max is greater, this is the greatest sum of the contiguous sub array.

Solution

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int local_max = 0;
        int global_max = INT_MIN;
        
        for(int i = 0; i < nums.size(); i++){
            local_max = max(nums[i], local_max + nums[i]);
            global_max = local_max > global_max ? local_max : global_max;
        }
        return global_max;
    }
};