All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Sumit's sub-array and sub-sequence
/
No tags
Problem
Editorial
Analytics

Given an array A of N elements, find the maximum possible sum of a

  • Contiguous subarray
  • Non-contiguous (not necessarily contiguous) subarray.

Empty subarrays/subsequences should not be considered.

Input :

  • First line of the input has an integer T. T cases follow.
  • Each test case begins with an integer N . In the next line,N integers follow representing the elements of array A.

Output :

  • Two, space separated, integers denoting the maximum contiguous and non-contiguous subarray. At least one integer should be selected and put into the subarrays

Constraints :

  • 1<=T<=10
  • 1<=N<=10^5
  • -10^4<=Ai<=10^4
SAMPLE INPUT
1
6
2 -1 2 3 4 -5
SAMPLE OUTPUT
10 11
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?