#codeifyoucansolve
Given an array A={a1,a2,…,aN} 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 Format

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.

Constraints:

1≤T≤10
1≤N≤105
−104≤ai≤104

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

Output Format

2 space separated integers denoting the maximum contiguous and non-contiguous subarray. At least one integer should be selected and put into the subarrays (this may be required in cases where all elements are negative).

Sample Input

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

Sample Output

10 10
10 11

Explanation

In the first case:
The max sum for both contiguous and non-contiguous elements is the sum of ALL the elements (as they are all positive).

In the second case:
[2 -1 2 3 4] –> This forms the contiguous sub-array with the maximum sum.
For the max sum of a not-necessarily-contiguous group of elements, simply add all the positive elements.

Copyright (c) 2015 HackerRank.
All Rights Reserved

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAX 100000
int main() {
    int T,flag;
    long int N;
    long int arr[MAX],i,max,max_1,max_2;
    scanf("%d",&T);
    while(T--)
        {
        scanf("%ld",&N);
        for(i=0;i<N;i++)
            scanf("%ld",&arr[i]);
        flag    =   max =   max_1 =  max_2   =   0;
        for(i=0;i<N;i++)
            {
            max     +=   arr[i];
            if(max<0)
                max  = 0;
            if(max_1<max)
                max_1 =   max;
            if(arr[i]>0)
                {
                max_2 += arr[i];
                flag    =   1;
            }
            
        }
        if(flag ==  0)
            printf("%ld %ld\n",arr[0],arr[0]);
        else
            printf("%ld %ld\n",max_1,max_2);
    }
    
    return 0;
}

********************************************************
Kadane’s Algorithm:

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far