Maximum Subarray Sum - Scaler Topics

Problem Statement

We are given an array A of size N which consists of both positive and negative integers. We have to write a program to find the Maximum Sum of Subarray.

Note: A subarray is a contiguous part of an Array.

Example

Input: [2,-3,6,-5,4,2]

Output: 7

Explanation: The subarray [6,-5,4,2] is the max sum contiguous subarray with sum 7.

Input: [-2, 5, -2, 3]

Output: 6

Explanation: The Subarray [5, -2, 3] is the max sum contiguous subarray with sum 6.

Constraints

What is a Subarray?

A subarray is a continuous part of the array which can be made by deleting zero or more elements from the beginning or can be made by deleting zero or more elements from the end or both sides.

Example:

Array: [1,3,5,6,2] Example of some subarrays: [1,3,5], [5,6,2], [3,5,6,2], [1], [1,3,5,6,2]

Approach 1: Brute Force Approach Using 3 Nested Loops

Algorithm:

Run a loop from i=0 to i=n-1
Run a nested loop inside the first loop from j=i to j=n-1
Run another nested loop inside the second loop from k=i to k=j
For each subarray calculate the currSum and finally maintain a variable (say maxSum) and each time the innermost loop and we will update the answer by maxSum = max(maxSum,currSum)

C++ Implementation

Java Implementation

Python Implementation

Complexity Analysis

Time Complexity Analysis

We can see that we are using 3 Nested Loops

1st loop will always run from 0 to n-1 i.e. N times
In the worst case 2nd loop will run from 0 to n-1 i.e. N times because when i=0, j will run from 0 to n-1.
In the worst case 3rd loop will run from 0 to n-1 i.e. N times because when i=0 and j=n-1, k will run from 0 to n-1

So the worst-case time complexity of this approach becomes O(N * N * N) i.e. O(N^3)

Space Complexity Analysis

We are only declaring variables that we consider as O(1) space, so its overall space complexity is O(1)

Time complexity: O(N^3) Space complexity: O(1)

Approach 2: Using two Nested Loops

Algorithm:

Run a loop from i=0 to i=n-1
Run a nested loop inside the first loop from j=i to j=n-1
For each subarray calculate the currSum and finally maintain a variable (say maxSum) and each time the innermost loop and we will update the answer by maxSum = max(maxSum,currSum)

C++ Implementation

Java Implementation

Python Implementation

Complexity Analysis

Time Complexity Analysis

We can see that we are using 2 nested loops

1st loop will always run from 0 to n-1 i.e. N times
In the worst case 2nd loop will run from 0 to n-1 i.e. N times because when i=0, j will run from 0 to n-1.

So the worst-case time complexity of this approach becomes O(N * N) i.e. O(N^2)

Space Complexity Analysis

We are only declaring variables that we consider as O(1) space, so its overall space complexity is O(1)

Time complexity: O(N^2) Space complexity: O(1)

Approach 3: Using the Divide and Conquer Algorithm

Algorithm:

Divide the given array into two halves
Initially, our range is from l=0 to h=n-1
At each step divide the array using m = (l+h)/2, where m is the middle index and now divide the array into two halves, one from l to m and another from m+1 to h
Calculate the following 3 values
1. Maximum Subarray Sum of the left half (By making a recursive call)
2. Maximum Subarray Sum of the right half (By making a recursive call)
3. Maximum Subarray Sum such that this subarray crosses the middle point of the array
Return the maximum of the above calculated 3 values

C++ Implementation

Java Implementation

Python Implementation

Complexity Analysis

Time Complexity Analysis

maximumSubarraySum() is a recursive function in which we are dividing the array into 2 equal parts, and we are calling the maxSumCrossingMiddle() function each time we divide the array, so the Time Complexity is as follows:

Each time maximumSubarraySum() is divided into 2 equal parts, so the time complexity of dividing the array into two parts, until its size becomes 0 is O(NlogN)
In the function maxSumCrossingMiddle(), first, i will run from m to l, then i will run from m+1 to h, so in the worst case i can run from 0 to n-1
So in maxSumCrossingMiddle() the Time Complexity will becon O(N+N) which is equivalent to O(N)

So the worst-case time complexity of this approach becomes O(N * LogN) i.e. O(NLogN)

Space Complexity Analysis

We are only declaring variables that we consider as O(1) space, so its overall space complexity is O(1)

Time complexity: O(N*LogN) Space complexity: O(1)

Approach 4: Using Kadane's Algorithm (Dynamic Programming)

Kadane’s Algorithm is a dynamic programming algorithm that can efficiently calculate the maximum subarray sum

Algorithm:

Initialize a variable named max_till_now=0
Initialize another variable max_ending_here=0
Follow the below steps at each index from i=0 to i=n-1
1. max_ending_here = max_ending_here + A[i]
2. if(max_ending_here>max_till now) max_till_now = max_ending_here
3. if(max_ending_here<0) max_ending_here=0
Return the variable max_till_now