The Maximum Subarray[HackerRank Solution] Dynamic Programming
Problem:
Given an array of N elements, find the maximum possible sum among
- all nonempty subarrays.
- all nonempty subsequences.
We define a subarray as a contiguous subsequence. Note that empty subarrays/subsequences should not be considered.
Input Format
The first line of input contains a single integer T denoting the number of test cases.
The first line of each test case contains a single integer N . The second line contains N space-separated integers denoting the elements of A.
Constraints
The subarray and subsequences you consider should have at least one element.
Output Format
Print two space-separated integers denoting the maximum sums of nonempty subarrays and nonempty subsequences, respectively.
Sample Input 0
2
4
1 2 3 4
6
2 -1 2 3 4 -5
Sample Output 0
10 10
10 11
Code:
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int t;
cin>>t;
while(t--){
int n,max1 =-1000;
int max2 = -1000;
cin>>n;
int a[n];
int sum = 0;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]>max1){
max1 = a[i];
}
if(a[i] >= 0){
sum+= a[i];
}
}
if(sum == 0){
sum =max1;
}
int maxSum = 0 , cursum = 0;
for(int i =0;i<n;i++){
cursum+= a[i];
if(cursum < 0){
cursum = 0;
}
else if(cursum > maxSum){
maxSum = cursum;
}
}
if(maxSum == 0){
maxSum =sum;
}
cout<<maxSum<<" "<< sum<<endl;
}
return 0;
}
Passed all test cases!
ADDITIONAL KNOWLEDGE 
Leave a comment