Maximum Subarray Sum Problem Statement

Given an array ARR consisting of N integers, your goal is to determine the maximum possible sum of a non-empty contiguous subarray within this array.

Example of Subarrays:

An array C is considered a subarray of array D if it can be obtained by deleting zero or more elements from the beginning and end of the array D. For instance, for the array [1, 2, 3], all non-empty subarrays are [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3].

Input:

N ARR[0] ARR[1] ... ARR[N-1]

Output:

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

Example:

Input:

5 -2 1 -3 4 -1

Output:

4

Explanation:

The subarray [4] has the maximum sum of any contiguous subarray.

Constraints:

1

Question

Maximum Subarray Sum Problem Statement

Given an array ARR consisting of N integers, your goal is to determine the maximum possible sum of a non-empty contiguous subarray within this array.

Example of Subarrays:

An array C is considered a subarray of array D if it can be obtained by deleting zero or more elements from the beginning and end of the array D. For instance, for the array [1, 2, 3], all non-empty subarrays are [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3].

Input:

N
ARR[0] ARR[1] ... ARR[N-1]

Output:

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

Example:

Input:

5
-2 1 -3 4 -1

Output:

Explanation:

The subarray [4] has the maximum sum of any contiguous subarray.

Constraints:

1 <= N <= 5*10⁵
-10⁹ <= ARR[i] <= 10⁹
Time Limit: 1 second

Note:

You do not need to print anything; it has already been taken care of. Implement the required function to find the solution.

Accepted Answer

Find the maximum sum of a contiguous subarray in an array of integers.

Use Kadane's algorithm to find the maximum subarray sum efficiently.
Initialize two variables: maxEndingHere and maxSoFar.
Iterate through the array and update the variables accordingly.
Return the maxSoFar as the result.

Asked in Accenture