Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Maximum Subarray Sum

Moderate
0/80
Average time to solve is 25m
43 upvotes
Asked in companies
AmazonSnapdealRazorpay

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 )
Constraints:
1 <= N <= 10^6
1 <= K <= N
Time limit: 1 sec 
Sample Input 1:
4 1
1 2 3 4
Sample Output 1:
4
Sample Input 2:
6 2
2 7 3 6 7 7 
Sample Output 2:
14

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
Full screen
Console