We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Practice
  2. Algorithms
  3. Dynamic Programming
  4. The Maximum Subarray

The Maximum Subarray

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

We define subsequence as any subset of an array. We define a subarray as a contiguous subsequence in an array.

Given an array, find the maximum possible sum among:

  1. all nonempty subarrays.
  2. all nonempty subsequences.

Print the two values as space-separated integers on one line.

Note that empty subarrays/subsequences should not be considered.

Example

The maximum subarray sum is comprised of elements at inidices . Their sum is . The maximum subsequence sum is comprised of elements at indices and their sum is .

Function Description

Complete the maxSubarray function in the editor below.

maxSubarray has the following parameter(s):

  • int arr[n]: an array of integers

Returns

  • int[2]: the maximum subarray and subsequence sums

Input Format

The first line of input contains a single integer , the number of test cases.

The first line of each test case contains a single integer .
The second line contains space-separated integers where .

Constraints

The subarray and subsequences you consider should have at least one element.

Sample Input 0

2
4
1 2 3 4
6
2 -1 2 3 4 -5

Sample Output 0

10 10
10 11

Explanation 0

In the first case: The maximum sum for both types of subsequences is just the sum of all the elements since they are all positive.

In the second case: The subarray is the subarray with the maximum sum, and is the subsequence with the maximum sum.

Sample Input 1

1
5
-2 -3 -1 -4 -6

Sample Output 1

-1 -1

Explanation 1

Since all of the numbers are negative, both the maximum subarray and maximum subsequence sums are made up of one element, .

Author

sh4d0wkn1ght

Difficulty

Medium

Max Score

50

Submitted By

68637

Need Help?


View discussions
View editorial
View top submissions
RESOURCES

  • Dynamic Programming Basics

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature