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 a given array of integers.

Use Kadane's algorithm for an efficient O(N) solution.
Initialize two variables: max_sum and current_sum.
Iterate through the array, updating current_sum and max_sum.
Example: For array [-2, 1, -3, 4, -1], max_sum is 4 from subarray [4].
Handle negative numbers by ensuring current_sum resets to 0 if it becomes negative.

Asked in Accenture