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;
}