QUESTION
Given an array containing both negative and positive integers. Find the contiguous sub-array with maximum sum.\n \nInput:\nThe first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated integers A1, A2, …, AN denoting the elements of the array.\n \nOutput:\nPrint the maximum sum of the contiguous sub-array in a separate line for each test case.\n \nConstraints:\n1 T 40\n1 N 100\n-100 A[i] <= 100.
“TESTCASE_1”: “2\n3\n1 2 3\n4\n-1 -2 -3 -4\n###—###SEPERATOR—###—\n6\n-1”, “TESTCASE_2”: “2\n3\n5 6 7\n4\n-5 -6 -7 -8 \n###—###SEPERATOR—###—\n18\n-5”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0
ANSWER
#include<iostream>
using namespace std;
int maxSubArraySum(int a[], int size)
{
int max_so_far = a[0];
int curr_max = a[0];
for (int i = 1; i < size; i++)
{
curr_max = max(a[i], curr_max+a[i]);
max_so_far = max(max_so_far, curr_max);
}
return max_so_far;
}
/* Driver program to test maxSubArraySum */
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int max_sum = maxSubArraySum(a, n);
cout << max_sum<<endl;
}
return 0;
}