Maximum Subarray  

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance Cisco Facebook Goldman Sachs Google JP Morgan JPMorgan LinkedIn Microsoft Oracle PayPal Paytm Uber
Array Divide and Conquer Dynamic Programming

In the Maximum Subarray problem we have given an integer array nums, find the contiguous sub array which has the largest sum and print the maximum sum subarray value.

Example  

Input
nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}
Output
6

Maximum SubarrayPin

Algorithm  

The goal is to find the maximum sum in a line(contiguous sub-array) in the nums array, which is achieved using Kadane’s Algorithm.
We use two global variables, max and maxTillNow, where max stores the final answer, and maxTillNow stores the maximum result till the ith index.
Initialize max and maxTillNow as nums[0], run a loop from 1 to n, during each iteration maxTillNow becomes maximum of nums[i] and (maxTillNow + nums[i]) and max becomes maximum of max and maxTillNow.
Finally, we return max, which stores the maximum subarray sum.

Please click Like if you loved this article?

Complexity Analysis  

Time Complexity = O(n) where n is the number of integer present in the given array.
Space Complexity = O(1)

Explanation for Maximum Subarray  

Consider the case where nums = {2, -1, 3, 5, -2, 1}
Initialize,

  • max = nums[0] = 2 and maxTillNow = 2
  • for i = 1, nums[i] = -1
    maxTillNow = max(-1, -1 + 2) = max(-1, 1) = 1
    max = max(2, 1) = 2
  • for i = 2, nums[i] = 3 for i = 4, nums[i] = -2
  • maxTillNow = max(-2, -2 + 9) = max(-2, 7) = 7
    max = max(9, 7) = 9
  • for i = 5, nums[i] = 1
    maxTillNow = max(1, 1 + 7) = max(1, 8) = 8
    max = max(9, 8) = 9
  • Loop ends and we return max as 9, which is the answer. Here 9 is our maximum subarray sum.
See also
Degree of an array

Pseudo Code

  1. Intialize max and maxTillNow as nums[0]
  2. loop for (i = 1 to less than n)
  3. maxTillNow = maximum(maxTillNow + nums[i], nums[i])
  4. max = maximum(max, maxTillNow)
  5. end for
  6. return max

JAVA Code for Maximum Subarray

public class MaximumSubarray {
    public static void main(String[] args) {
        // Input array
        int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        
        // Find the maximum subarray using Kadane's algorithm
        int maxSum = findMaxSubarray(nums);
        
        // Print the answer
        System.out.println(maxSum);
    }
    
    private static int findMaxSubarray(int[] nums) {
        // Initialise max and maxTillNow as nums[0]
        int max = nums[0];
        int maxTillNow = nums[0];
        
        // Loop through the array
        for (int i = 1; i < nums.length; i++) {
            // maxTillNow is max of curr element or maxTillNow + curr element
            maxTillNow = Math.max(nums[i], maxTillNow + nums[i]);
            // max is maximum of max and maxTillNow
            max = Math.max(max, maxTillNow);
        }
        
        // Return the result
        return max;
    }
}

C++ Code for Maximum Subarray

#include <bits/stdc++.h>
using namespace std;

int findMaxSubarray(int *nums, int n) {
    // Initialise max and maxTillNow as nums[0]
    int max = nums[0];
    int maxTillNow = nums[0];
    
    // Loop through the array
    for (int i = 1; i < n; i++) {
        // maxTillNow is max of curr element or maxTillNow + curr element
        maxTillNow = std::max(nums[i], maxTillNow + nums[i]);
        // max is maximum of max and maxTillNow
        max = std::max(max, maxTillNow);
    }
    
    // Return the result
    return max;
}

int main() {
    // Input array
    int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    
    int n = sizeof(nums) / sizeof(*nums);
    
    // Find the maximum subarray using Kadane's algorithm
    int maxSum = findMaxSubarray(nums, n);

    // Print the answer
    cout<<maxSum<<endl;
    
    return 0;
}
{-2, 1, -3, 4, -1, 2, 1, -5, 4}
6

References

Please click Like if you loved this article?