Maximum Subarray Sum

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.

CodingNinjas
author
2y

Tip 1 : Used dictionary to find the sum of the number.

CodingNinjas
author
2y
Brute Force 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
  2. The inner loop will go from j = i to j = i + k - 1. Thi...read more
CodingNinjas
author
2y
BST Approach
  1. Create a BST and insert the first k elements in it
  2. Print the largest element in the tree
  3. Now iterate through the remaining elements of the tree:
    1. Insert the current element in the BST
    2. Delete th...read more
CodingNinjas
author
2y
Deque Approach
  1. Create a double ended queue. Note that the deque will store the indices of the elements, not the elements themselves
  2. Insert the first k elements (the first subarray) in the deque. While i...read more
Add answer anonymously...
Vinove Software & Services Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions
Get AmbitionBox app

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter