Maximum Subarray Problem Statement

Ninja has been given an array, and he wants to find a subarray such that the sum of all elements in the subarray is maximum.

A subarray 'A' is considered greater than a subarray 'B' if sum(A) > sum(B). If two subarrays have the same maximum sum, choose the subarray with the larger length.

Explanation:

A subarray is a contiguous part of an array. For example, in an array arr = [1, 2, 3, 4], [1, 2], and [2, 3, 4] are contiguous subarrays, but [1, 3, 4] is not.

Input:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a single integer ‘N’ denoting the size of the array.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array.

Output:

For each case, if the returned subarray is correct then print 1, else print 0.

The output of each test case will be printed in a separate line.

Example:

Example 1:
Input: T = 1, N = 4, arr = [1, 2, -1, 3]
Output: 1
Explanation: The subarray [1, 2, -1, 3] has the maximum sum of 5.

Constraints:

  • 1 ≤ T ≤ 5
  • 1 ≤ N ≤ 1000
  • -99 ≤ |arr| ≤ 99
  • Time limit: 1 sec.

Note:

You do not need to input or print anything, it has already been taken care of. Just implement the given function.

AnswerBot
1y

The problem is to find a subarray with the maximum sum in a given array.

  • Iterate through the array and keep track of the maximum sum and the current sum.

  • If the current sum becomes negative, reset it to...read more

Help your peers!
Add answer anonymously...
Swiggy 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

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