DEV Community

loading...

LeetCode - Maximum Subarray

Alkesh Ghorpade
Ruby on Rails and Golang consultant
Originally published at alkeshghorpade.me ・3 min read

Container

Problem statement

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

Problem statement taken from: https://leetcode.com/problems/maximum-subarray

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.
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: nums = [1]
Output: 1
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: nums = [5, 4, -1, 7, 8]
Output: 23
Enter fullscreen mode Exit fullscreen mode

Constraints:

- 1 <= nums.length <= 3 * 10^4
- -10^5 <= nums[i] <= 10^5
Enter fullscreen mode Exit fullscreen mode

Explanation

Brute force

The brute force approach is to generate all subarrays and
print that subarray which has a maximum sum.

A C++ snippet of the above logic is as below:

for (int i = 0; i < n; i++){
    for (int j = i; j < n; j++){
        for (int k = i; k <= j; k++){
            // calculate sum of all the elements
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

The time complexity of the above approach is O(N^3).
We can improve the above logic using
Kadane algorithm.

Kadane algorithm

The simple idea of Kadane’s algorithm is to look for all positive contiguous segments
of the array (max_sum is used for this).
And keep track of maximum sum contiguous segment among all positive segments
(max_sum_so_far is used for this).
Each time we get a positive sum compare it with max_sum and
update max_sum if it is greater than max_sum_so_far.

Let's check the algorithm below:

- set max_sum_so_far = 0, max_sum = INT_MIN

- Loop for i = 0; i < nums.length; i++
  - add max_sum_so_far = max_sum_so_far + nums[i]

  - if max_sum < max_sum_so_far
    - set max_sum = max_sum_so_far

  - if max_sum_so_far < 0
    - set max_sum_so_far = 0

- return max_sum
Enter fullscreen mode Exit fullscreen mode

The time complexity of the above approach is O(N) and,
space complexity is O(1).

C++ solution
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_sum = INT_MIN;
        int max_sum_so_far = 0;

        for(int i = 0; i < nums.size(); i++){
            max_sum_so_far += nums[i];

            if(max_sum < max_sum_so_far){
                max_sum = max_sum_so_far;
            }

            if(max_sum_so_far < 0){
                max_sum_so_far = 0;
            }
        }

        return max_sum;
    }
};
Enter fullscreen mode Exit fullscreen mode
Golang solution
func maxSubArray(nums []int) int {
    maxSum := math.MinInt32
    maxSumSoFar := 0

    for i := 0; i < len(nums); i++ {
        maxSumSoFar += nums[i]

        if maxSum < maxSumSoFar {
            maxSum = maxSumSoFar
        }

        if maxSumSoFar < 0 {
            maxSumSoFar = 0
        }
    }

    return maxSum
}
Enter fullscreen mode Exit fullscreen mode
Javascript solution
var maxSubArray = function(nums) {
    let maxSumSoFar = 0;
    let maxSum = -Infinity;

    if(nums.length === 0) return 0;
    if(nums.length === 1) return nums[0]

    for( let i = 0; i<nums.length; i++) {
        maxSumSoFar += nums[i];

        maxSum = Math.max(maxSum, maxSumSoFar);

        if(maxSumSoFar < 0) {
            maxSumSoFar = 0;
        }
    }

    return maxSum;
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm to see how the solution works.

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

Step 1: max_sum_so_far = 0
        max_sum = INT_MIN

Step 2: for i = 0; i < nums.length
        0 < 9
        true

        max_sum_so_far += nums[0]
        max_sum_so_far = 0 + -2
        max_sum_so_far = -2

        max_sum < max_sum_so_far
        -2^31 - 1 < -2
        true

        max_sum = max_sum_so_far
        max_sum = -2

        max_sum_so_far < 0
        -2 < 0
        true

        max_sum_so_far = 0

        i++
        i = 1

Step 3: i < nums.length
        1 < 9
        true

        max_sum_so_far += nums[1]
        max_sum_so_far = 0 + 1
        max_sum_so_far = 1

        max_sum < max_sum_so_far
        -2 < 1
        true

        max_sum = max_sum_so_far
        max_sum = 1

        max_sum_so_far < 0
        1 < 0
        false

        i++
        i = 2

Step 4: i < nums.length
        2 < 9
        true

        max_sum_so_far += nums[2]
        max_sum_so_far = 1 + -3
        max_sum_so_far = -2

        max_sum < max_sum_so_far
        1 < -2
        false

        max_sum_so_far < 0
        -2 < 0
        true

        max_sum_so_far = 0

        i++
        i = 3

Step 5: i < nums.length
        3 < 9
        true

        max_sum_so_far += nums[3]
        max_sum_so_far = 0 + 4
        max_sum_so_far = 4

        max_sum < max_sum_so_far
        1 < 4
        true

        max_sum = max_sum_so_far
        max_sum = 4

        max_sum_so_far < 0
        false

        i++
        i = 4

Step 6: i < nums.length
        4 < 9
        true

        max_sum_so_far += nums[4]
        max_sum_so_far = 4 + -1
        max_sum_so_far = 3

        max_sum < max_sum_so_far
        4 < 3
        false

        max_sum_so_far < 0
        false

        i++
        i = 5

Step 7: i < nums.length
        5 < 9
        true

        max_sum_so_far += nums[5]
        max_sum_so_far = 3 + 2
        max_sum_so_far = 5

        max_sum < 5
        4 < 5
        true

        max_sum = max_sum_so_far
        max_sum = 5

        max_sum_so_far < 0
        false

        i++
        i = 6

Step 8: i < nums.length
        6 < 9
        true

        max_sum_so_far += nums[6]
        max_sum_so_far = 5 + 1
        max_sum_so_far = 6

        max_sum < 6
        5 < 6
        true

        max_sum = max_sum_so_far
        max_sum = 6

        max_sum_so_far < 0
        false

        i++
        i = 7

Step 9: i < nums.length
        7 < 9
        true

        max_sum_so_far += nums[7]
        max_sum_so_far = 6 + -5
        max_sum_so_far = 1

        max_sum < 6
        6 < 1
        false

        max_sum_so_far < 0
        false

        i++
        i = 8

Step 10: i < nums.length
         8 < 9
         true

         max_sum_so_far += nums[8]
         max_sum_so_far = 1 + 4
         max_sum_so_far = 5

         max_sum < 6
         6 < 5
         false

         max_sum_so_far < 0
         false

         i++
         i = 9

Step 11: i < nums.length
         9 < 9
         false

Step 12: return max_sum
         Answer is 6
Enter fullscreen mode Exit fullscreen mode

Discussion (0)