Last Updated: 2 Sep, 2019
Maximum Subarray Sum
Moderate
Asked in companies
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.
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
Approaches
- 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.
- Create a BST and insert the first k elements in it
- Print the largest element in the tree
- Now iterate through the remaining elements of the tree:
- Insert the current element in the BST
- Delete the one element that is not part of the current subarray
- Print the largest element in the tree
- Create a double ended queue. Note that the deque will store the indices of the elements, not the elements themselves
- Insert the first k elements (the first subarray) in the deque. While inserting the current element, check if the element at the back of the queue is smaller than the current element. If yes, then remove all those elements and then insert the current element in the back of deque.
- After you’ve done this, the front of the queue will have the maximum element in the first subarray. Print the front element of the deque.
- Then, we’ll follow the same idea for the next elements as well but there will be one extra step which is to remove all elements from the front of the deque that are out of the range of the subarray in consideration.
Similar problems