Maximum Subarray Sum Problem Statement

Given an array of integers, determine the maximum possible sum of any contiguous subarray within the array.

Example:

Input:

array = [34, -50, 42, 14, -5, 86]

Output:

137

Explanation:

The maximum sum is achieved by the subarray [42, 14, -5, 86].

Input:

array = [-5, -1, -8, -9]

Output:

-1

Explanation:

The maximum sum is -1, achieved by the subarray [-1].

Constraints:

1 ≤ N ≤ 10⁶, where N is the number of elements in the array.

-10⁴ ≤ array[i] ≤ 10⁴

Note:

The solution should have a time complexity of O(N).

Input:

The first line contains a single integer, N, the size of the array. The second line contains N space-separated integers representing the elements of the array.

Output:

A single integer, the maximum subarray sum.

Question

Maximum Subarray Sum Problem Statement

Given an array of integers, determine the maximum possible sum of any contiguous subarray within the array.

Example:

Input:

array = [34, -50, 42, 14, -5, 86]

Output:

Explanation:

The maximum sum is achieved by the subarray [42, 14, -5, 86].

Input:

array = [-5, -1, -8, -9]

Output:

-1

Explanation:

The maximum sum is -1, achieved by the subarray [-1].

Constraints:

1 ≤ N ≤ 10⁶, where N is the number of elements in the array.
-10⁴ ≤ array[i] ≤ 10⁴

Note:

The solution should have a time complexity of O(N).

Input:

The first line contains a single integer, N, the size of the array. The second line contains N space-separated integers representing the elements of the array.

Output:

A single integer, the maximum subarray sum.

Accepted Answer

Find the maximum sum of any contiguous subarray within an array of integers.

Iterate through the array and keep track of the maximum sum of subarrays encountered so far.
At each index, decide whether to include the current element in the subarray or start a new subarray.
Use Kadane's algorithm to efficiently find the maximum subarray sum.
Example: For array [34, -50, 42, 14, -5, 86], the maximum subarray sum is 137.

Maximum Subarray Sum Problem Statement

Example:

Input:

Output:

Explanation:

Input:

Output:

Explanation:

Constraints:

Note:

Input:

Output:

HashedIn by Deloitte Software Developer interview questions & answers

Popular interview questions of Software Developer