Maximum Sum Subarray Problem Statement

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

Example:

Input:

array = [34, -50, 42, 14, -5, 86]

Output:

137

Explanation:

The maximum sum of a contiguous subarray is 137, which is the sum of the elements [42, 14, -5, 86].

Input:

array = [-5, -1, -8, -9]

Output:

-1

Explanation:

The maximum sum of a contiguous subarray is -1, as choosing any subarray cannot yield a greater sum.

Input:

N
array of N space-separated integers

Output:

Maximum sum of any contiguous subarray

Constraints:

1 ≤ N ≤ 10⁵

-10⁴ ≤ array[i] ≤ 10⁴

Note:

The solution should be accomplished in O(N) time complexity.

Question

Maximum Sum Subarray Problem Statement

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

Example:

Input:

array = [34, -50, 42, 14, -5, 86]

Output:

Explanation:

The maximum sum of a contiguous subarray is 137, which is the sum of the elements [42, 14, -5, 86].

Input:

array = [-5, -1, -8, -9]

Output:

-1

Explanation:

The maximum sum of a contiguous subarray is -1, as choosing any subarray cannot yield a greater sum.

Input:

N
array of N space-separated integers

Output:

Maximum sum of any contiguous subarray

Constraints:

1 ≤ N ≤ 10⁵
-10⁴ ≤ array[i] ≤ 10⁴

Note:

The solution should be accomplished in O(N) time complexity.

Accepted Answer

Find the maximum sum of any contiguous subarray within an array in O(N) time complexity.

Use Kadane's algorithm to find the maximum sum subarray in O(N) time complexity
Initialize max_sum and current_sum to the first element of the array
Iterate through the array, updating current_sum and max_sum as needed
Return max_sum as the maximum sum of any contiguous subarray

Accepted Answer

1 person

Accepted Answer

The direct approach to solve this problem is to run two for loops and for every subarray check if it is the maximum sum possible. 
Time complexity: O(N^2), Where N is the size of the array.
Space complexity: O(1)

The efficient approach is to use Kadane's algorithm. It calculates the maximum sum subarray ending at a particular index by using the maximum sum subarray ending at the previous position. 
Steps : 
Declare two variables : currSum which stores maximum sum ending here and maxSum which stores maximum sum so far.
Initialize currSum = 0 and maxSum = INT_MIN.
Now, traverse the array and add the value of the current element to currSum and check : 
1. If currSum > maxSum, update maxSum equals to currSum.
2. If currSum < 0, make currSum equal to zero.
Finally, print the value of maxSum.

Reply

2y

Brute Force ApproachCreate a nested loop. The outer loop will go from i = 0 to i = n - k. This will cover the starting indices of all k-subarraysThe inner loop will go from j = i to j = i + k - 1. Thi...
see more

Reply

2y

BST ApproachCreate a BST and insert the first k elements in itPrint the largest element in the treeNow iterate through the remaining elements of the tree:Insert the current element in the BSTDelete th...
see more

Reply

2y

Deque ApproachCreate a double ended queue. Note that the deque will store the indices of the elements, not the elements themselvesInsert the first k elements (the first subarray) in the deque. While i...nonymously

Asked in Tech Mahindra