# Maximum Subarray Sum

Posted: 2 Sep, 2019

Difficulty: Moderate

#### 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.

Approach 1

- 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.

Approach 2

Approach 3

- 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

# Connecting Ropes

Posted: 12 Nov, 2021

Difficulty: Hard

# Insertion Sort

Posted: 30 Nov, 2021

Difficulty: Easy

# Subarrays With Zero Sum

Posted: 1 Dec, 2021

Difficulty: Easy

# Find Student

Posted: 1 Dec, 2021

Difficulty: Easy

# Smaller Than Triplet Sum

Posted: 1 Dec, 2021

Difficulty: Moderate