Maximum Subarray Sum

Moderate

0/80

Average time to solve is 25m

60 upvotes

Asked in companies

Problem statement

Given an array of numbers, find the maximum sum of any contiguous subarray of the array.

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.

Given the array [-5, -1, -8, -9], the maximum sum would be -1.

Follow up: Do this in O(N) time.

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

Input format:

The first line of input contains size of array, which is denoted by N and second line of input contains N space separated integers.

Output format:

The first and only line of output should print the maximum subarray sum, as described in the description.

Constraints:

1 <= N <= 10^6
1 <= K <= N
Time limit: 1 sec

Sample Input 1:

4 1
1 2 3 4

Sample Output 1:

Sample Input 2:

6 2
2 7 3 6 7 7

Sample Output 2:

Explanation for Sample Output 2:

There are 5 subarrays of size 2 in this array. They are {2, 7}, {7, 3}, {3, 6}, {6, 7}, {7, 7}. Since the subarray {7, 7} has the maximum sum among all the subarrays, the output will be 7 + 7 = 14

Hint 1

Hint 2

Hint 3

Is there a way to just check all k-subarrays one by one and find the maximum element for each?

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force Approach

Create a nested loop. The outer loop will go from i = 0 to i = n - k. This will cover the starting indices of all k-subarrays
The inner loop will go from j = i to j = i + k - 1. This will cover all the elements of the k-subarray starting from index i
Keep track of the maximum element in the inner loop and print it.

Time Complexity

O(N * K) where N is the length of the input array and K is the size of the subarray.

Space Complexity

O(1) because the extra space being used (looping variables, maximum element) is constant for any N and K

(100% EXP penalty)

Maximum Subarray Sum

Console