Maximum Subarray Sum Problem Statement

Given an array arr of length N consisting of integers, find the sum of the subarray (including empty subarray) with the maximum sum among all subarrays.

Explanation:

A subarray is a contiguous segment of an array, meaning it can be formed by removing 0 or more integers from the start, and 0 or more integers from the end of the array.

Input:

N arr[0] arr[1] ... arr[N-1]

Output:

The sum of the maximum subarray.

Example:

Input:

N = 5 arr = [-2, 1, -3, 4, -1]

Output:

4

Explanation:

The maximum subarray sum is obtained by the subarray [4] which has the sum 4.

Constraints:

1

Question

Maximum Subarray Sum Problem Statement

Given an array arr of length N consisting of integers, find the sum of the subarray (including empty subarray) with the maximum sum among all subarrays.

Explanation:

A subarray is a contiguous segment of an array, meaning it can be formed by removing 0 or more integers from the start, and 0 or more integers from the end of the array.

Input:

N
arr[0] arr[1] ... arr[N-1]

Output:

The sum of the maximum subarray.

Example:

Input:

N = 5
arr = [-2, 1, -3, 4, -1]

Output:

Explanation:

The maximum subarray sum is obtained by the subarray [4] which has the sum 4.

Constraints:

1 <= N <= 10^6
-10^6 <= arr[i] <= 10^6

Note:

The sum of an empty subarray is considered 0.

Accepted Answer

Hamburger Menu
AmbitionBox Logo

Search
community
Asked inInfosys,System Engineer

Maximum Subarray Sum
You are given an array (ARR) of length N, consisting of integers. You have to find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.
A subarray is a contiguous segment of an array. In other words, a subarray can be formed by removing 0 or more integers from the beginning, and 0 or more integers from the end of an array.
Note :
The sum of an empty subarray is 0.
Input Format :
The first line of input contains an integer N, representing the length of the array. The second line of input contains N single space-separated integers, denoting the elements of the array.
Output Format :
In the only output line, output the maximum subarray sum.

Accepted Answer

Maximum Subarray Sum
You are given an array (ARR) of length N, consisting of integers. You have to find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.
A subarray is a contiguous segment of an array. In other words, a subarray can be formed by removing 0 or more integers from the beginning, and 0 or more integers from the end of an array.
Note :
The sum of an empty subarray is 0.
Input Format :
The first line of input contains an integer N, representing the length of the array. The second line of input contains N single space-separated integers, denoting the elements of the array.
Output Format :
In the only output line, output the maximum subarray sum.
Note :
You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
Constraints :
1 <= N <= 10^6 -10^6 <= A[i] <= 10^6 where N is the length of the array. A[i] represents the numbers present in the array. Time limit: 1sec

Accepted Answer

Divide And Conquer Approach
Divide the array into 2 halves.
Get the answer of left and right parts of the array by recursion.
Get the answer of Maximum subarray sum such that the subarray crosses the midpoint.
To find the maximum subarray sum of crossing points we need to find the maximum sum starting from mid point and ending at some point on the left of mid, then find the maximum sum starting from mid + 1 and ending with some point on right of mid + 1. Total sum would be the sum of both left part and right part.
Maximum of all three sums would be the final answer.
Space Complexity: O(n)Explanation:
O(N), where N is the length of the array.

The stack space is used for recursion.

Time Complexity: O(nlogn)Explanation:
O(N*logN), where N is the length of the array.

Because we are dividing our array to two subarrays and in each call for calculating the crossing sum through mid it is taking O(n) time.

T(n) = 2T(n/2) + O(n)

Thus, T(n) = O(nlogn)

Reply

Accepted Answer

Hamburger Menu
AmbitionBox Logo

Search
companycommunity
Asked inInfosys,System Engineer

Maximum Subarray Sum
You are given an array (ARR) of length N, consisting of integers. You have to find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.
A subarray is a contiguous segment of an array. In other words, a subarray can be formed by removing 0 or more integers from the beginning, and 0 or more integers from the end of an array.
Note :
The sum of an empty subarray is 0.
Input Format :
The first line of input contains an integer N, representing the length of the array. The second line of input contains N single space-separated integers, denoting the elements of the array.
Output Format :
In the only output line, output the maximum subarray sum.
Note :
You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
Constraints :
1 <= N <= 10^6 -10^6 <= A[i] <= 10^6 where N is the length of the array. A[i] represents the numbers present in the array. Time limit: 1sec

Accepted Answer

https://private-user-images.githubusercontent.com/77439575/313376671-821a6f9b-1355-4db1-ba1e-258d8d71195e.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MTA1NjgxMTQsIm5iZiI6MTcxMDU2NzgxNCwicGF0aCI6Ii83NzQzOTU3NS8zMTMzNzY2NzEtODIxYTZmOWItMTM1NS00ZGIxLWJhMWUtMjU4ZDhkNzExOTVlLnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDAzMTYlMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwMzE2VDA1NDMzNFomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPTU4M2YyZDU2YmI2NDI5NWZlZDhlNWQ1MGUxZGMyMTVlZDljNmM4MTE5MGJmZjMwOTU1ZjRmNzgzYmVlZWZlMDMmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.nSQMTOcAuHwbNuo9SvrBeiHdiSMErt5AH3bLW7mglDw