Subarray with Largest Possible Sum

Easy

0/40

1 upvote

Asked in company

Problem statement

You are given an array 'arr' of 'n' integers.

Your task is to find the starting and ending indices of a contiguous subarray that has the largest possible sum.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'n', representing the size of the array.

The second line contains 'n' space-separated integers, representing the elements of the array 'arr'.

Output Format:

Print two space-separated integers, start_index and end_index, which are the 0-based indices of the start and end of the maximum sum subarray.

Note:

If there are multiple subarrays with the same maximum sum, return the indices of the one that appears first (i.e., with the smallest starting index).

If the array contains all negative numbers, the subarray with the maximum sum will be the single element that is the largest (closest to zero).

Sample Input 1:

9
-2 1 -3 4 -1 2 1 -5 4

Sample Output 1:

3 6

Explanation for Sample 1:

The contiguous subarray [4, -1, 2, 1] has the largest sum of 6. Its starting index is 3 and its ending index is 6.

Sample Input 2:

5
1 2 3 4 5

Sample Output 2:

0 4

Explanation for Sample 2:

When all elements are positive, the maximum sum subarray is the entire array itself.

Expected Time Complexity:

The expected time complexity is O(n).

Constraints:

1 <= n <= 10^5
-10^9 <= arr[i] <= 10^9
Time limit: 1 sec

Approaches (1)

Approach 1

Subarray with Largest Possible Sum

Time Complexity

The expected time complexity is O(n)

Space Complexity

(100% EXP penalty)

Subarray with Largest Possible Sum

Console