Maximum Subarray Sum
You are given an array/list ARR consisting of N integers. Your task is to find the maximum possible sum of a non-empty subarray(contagious) of this array.

Note: An array C is a subarray of array D if it can be obtained by deletion of several elements(possibly zero) from the beginning and the end of array D.

For e.g.- All the non-empty subarrays of array [1,2,3] are [1], [2], [3], [1,2], [2,3], [1,2,3].

Input Format

The first line of input contains a single integer ‘N’ denoting the number of elements in the array/list. The second line of input contains ‘N’ single space-separated integers, denoting the elements of the array.

Output Format :

Print the maximum possible sum of any subarray of the array/list. Note: You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Maximum Subarray Sum

You are given an array/list ARR consisting of N integers. Your task is to find the maximum possible sum of a non-empty subarray(contagious) of this array.

Note: An array C is a subarray of array D if it can be obtained by deletion of several elements(possibly zero) from the beginning and the end of array D.

For e.g.- All the non-empty subarrays of array [1,2,3] are [1], [2], [3], [1,2], [2,3], [1,2,3].

Input Format

The first line of input contains a single integer ‘N’ denoting the number of elements in the array/list.

The second line of input contains ‘N’ single space-separated integers, denoting the elements of the array.

Output Format :

Print the maximum possible sum of any subarray of the array/list. 

Note: You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= N <= 5*10^5
-10^9 <= ARR[i] <=10^9

Time Limit: 1sec

Accepted Answer

Approach (Using Kadane's Algo) :

1) Declare a variable ‘maxSum’ and initialize it with ‘minimum integer’.

2) Declare a variable ‘localSum’ and initialize it with ‘0’.

3) Declare 3 counter variables as ‘start’ , ‘end’ , ‘newStart’ as 0, 0, 0.

4) Run a loop from i = 0 to N
4.1) Add a current element to ‘localSum’.

4.2) If 'localSum' is greater than 'maxSum'
Update ‘maxSum’ with 'localSum', update start with ‘newStart’ and end with loop counter ‘i’.

4.3) If 'localSum' is equal to ‘maxSum’ and the difference between ‘end’ and ‘start’ is less than the difference between ‘newStart’ and ‘i’
Update start with ‘newStart’ and end with ‘i’.

4.4) If 'localSum' is below ‘0’
Update ‘localSum’ as 0 and set ‘newStart' as ‘i’ + 1.

5) Return the part of the array starting from ‘start’ and ending at ‘end’.

TC : O(N), where N=size of the array
SC : O(N), we need a final array to store the result maximum subarray.

Accepted Answer

Brute Force

We will iterate through all possible boundaries of the subarrays in the given array with the help of two nested loops.

Then, we will iterate through each subarray with the help of another loop and find the sum of the subarray. We will maintain the maximum subarray sum through our iterations and finally return it.

Space Complexity: O(1)Explanation:

O(1), constant space is used.

Time Complexity: O(n^3)Explanation:

O(N^3), where N denotes the number of elements in an array.

As there are N*(N+1)/2 subarrays in total, and we are iterating over every subarray in linear time, the overall time complexity will be O(N^3).

C++ (g++ 5.4)

/*
    Time Complexity: O(N^3)
    Space Complexity: O(1)
    
    where N is the length of the array.
*/


long long maxSubarraySum(int arr[], int N)
{
	long long maxSum = -1e15;

	// Loop to traverse starting index of each subarray
	for(int i = 0; i < N; i++)
	{
		long long currSum = 0;	

		// Loop to traverse ending index of each subarray
		for(int j = i; j < N; j++)
		{
			long long currSum = 0;

			for(int k = i; k <= j; k++)
			{
				currSum += arr[k];
			}

			maxSum = max(maxSum, currSum);
		}
	}

	return maxSum;
}

Python (3.5)

'''

    Time Complexity: O(N^3)

    Space Complexity: O(1)

    

    where N is the length of the array.

'''





def maxSubarraySum(arr, N):



    maxSum = -1e15



    # Loop to traverse starting index of each subarray

    for i in range(N):



        # Loop to traverse ending index of each subarray

        for j in range(i, N):

            currSum = 0



            for k in range(i, j + 1):

                currSum += arr[k]



            maxSum = max(currSum, maxSum)



    return maxSum

Accepted Answer

Brute Force Optimized

We will iterate through all possible subarrays of the array with the help of two nested loops. We will maintain the maximum subarray sum/answer through our iterations and finally return it.

The algorithm will be-

We will run a loop for the starting index of the subarray.
From every starting index, we will run a loop for the ending index of the subarray.
- We will maintain a variable ‘currSum’ for the sum of the current subarray.
- Let the current ending index be ‘currIndex’. Then for each iteration, we will add ARR[currIndex] to currSum.
The maximum value of the variable ‘currSum’ encountered will be our answer.

Space Complexity: O(1)Explanation:

O(1), constant space is used.

Time Complexity: O(n^2)Explanation:

O(N^2), where N denotes the number of elements in an array.

We are visiting all the subarrays with the help of two nested loops. As there are N*(N+1)/2 subarrays in total, the time complexity will be O(N^2).

C++ (g++ 5.4)

/*
    Time Complexity: O(N^2)
    Space Complexity: O(1)
    
    where N is the length of the array.
*/


long long maxSubarraySum(int arr[], int N)
{
	long long maxSum = -1e15;

	// Loop to traverse starting index of each subarray
	for(int i = 0; i < N; i++)
	{
		long long currSum = 0;	

		// Loop to traverse ending index of each subarray
		for(int j = i; j < N; j++)
		{
			currSum += arr[j];

			if(currSum > maxSum)
			{
				maxSum = currSum;
			}
		}
	}

	return maxSum;
}

Python (3.5)

'''

    Time Complexity: O(N^2)

    Space Complexity: O(1)

    

    where N is the length of the array.

'''





def maxSubarraySum(arr, N):



    maxSum = -1e15



    # Loop to traverse starting index of each subarray

    for i in range(N):

        currSum = 0



        # Loop to traverse ending index of each subarray

        for j in range(i, N):

            currSum += arr[j]



            if currSum > maxSum:

                maxSum = currSum



    return maxSum

Accepted Answer

Kadane's Algorithm

The main observation here is that the optimal subarray will have no prefix with a negative sum. This is because we can remove the prefix with a negative sum from our optimal subarray which will only increase our subarray sum/answer.

The algorithm will be -

We will iterate through the array. We will maintain the variable ‘currSum’ denoting the maximum sum of prefix elements. Let the current index be ‘currIndex’.
For each iteration, we will-
- Add ARR[currIndex] to currSum.
- If currSum becomes negative, we will set the value of currSum to 0.
The maximum value of the variable ‘currSum’ encountered will be our answer.

Space Complexity: O(1)Explanation:

O(1), constant space is used.

Time Complexity: O(n)Explanation:

O(N), where N denotes the number of elements in an array.

As every index will be visited at most once, the time complexity will be O(N).

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(1)

    where N is the length of the array.
*/


long long maxSubarraySum(int arr[], int N)
{
    long long maxSum = -1e15;
    long long curSum = 0;

    for(int i = 0; i < N; i++)
    {
        curSum += arr[i];
        maxSum = max(maxSum, curSum);

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

    return maxSum;
}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(1)



    where N is the length of the array.

'''





def maxSubarraySum(arr, N):



    maxSum = -1e15

    curSum = 0



    for i in range(N):

        curSum += arr[i]

        maxSum = max(maxSum, curSum)



        if curSum < 0:

            curSum = 0;



    return maxSum

You are given an array/list ARR consisting of N integers. Your task is to find the maximum possible sum of a non-empty subarray(contagious) of this array.

Note: An array C is a subarray of array D if it can be obtained by deletion of several elements(possibly zero) from the beginning and the end of array D.

For e.g.- All the non-empty subarrays of array [1,2,3] are [1], [2], [3], [1,2], [2,3], [1,2,3].

Input Format

Output Format :

Constraints:

Top Capita Software Developer interview questions & answers

Popular interview questions of Software Developer