The Maximum Subarray

                            Solution in C :

In C++ :





#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main()
{
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int loop;
    cin >> loop;
    while (loop--) {
        int size;
        cin >> size;
        vector<int> data(size, 0);
        for (int i = 0; i < size; ++i) {
            cin >> data[i];
        }

        vector<int> dp(size, 0);
        int big = 0;
        int sum = 0;
        int start = -1;
        for (int i = 0; i < size; i++) {
            int val = sum + data[i];

            if (val > 0) {
                if (sum == 0) {
                    start = i;
                }
                sum = val;
            } else {
                sum = 0;
            }

            if (sum > big) {
                big = sum;
            }
        }

        if (start == -1) {
            cout << data[0] << " ";
        } else {
            cout << big << " ";
        }

        sum = 0;
        start = -1;
        for (int i = 0; i < size; ++i) {
            if (data[i] > 0) {
                start = i;
                sum += data[i];
            }
        }

        if (start == -1) {
            cout << data[0] << endl;
        } else {
            cout << sum << endl;
        }
    }
    return 0;
}








In Java :





import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner myScan = new Scanner(System.in);
        int T = myScan.nextInt();
        while(T--!=0){
        	int N = myScan.nextInt();
        	int[] arr = new int[N];
        	for(int i=0; i<N; i++){
        		arr[i]=myScan.nextInt();
        	}
        	int curr_sum=0;
        	int best_sum=0;
        	int non_cont_sum=0;
        	for(int j=0; j<N; j++){
        		curr_sum += arr[j];
        		if(curr_sum>0){
        			if(curr_sum>best_sum){
        				best_sum=curr_sum;
        			}
        		}else{
        			curr_sum=0;
        		}
        		if(arr[j]>0){
        			non_cont_sum +=arr[j];
        		}
        	}
        	if(best_sum ==0 && non_cont_sum==0){
        		int max = arr[0];
        		for(int l=1; l<N; l++){
        			if(arr[l]>max){
        				max=arr[l];
        			}
        		}
        		best_sum=max;
        		non_cont_sum=max;
        	}
        	System.out.print(best_sum+" "+non_cont_sum);
        	System.out.println();
        }
    }
}








In C :





#include <stdio.h>
#include <stdlib.h>
long long dp[100000];

int main(){
  long long a,T,N,ans1,ans2,max,i;
  scanf("%lld",&T);
  while(T--){
    ans1=ans2=0;
    max=-999999;
    scanf("%lld",&N);
    for(i=0;i<N;i++){
      scanf("%lld",&a);
      if(a>max)
        max=a;
      if(a>0)
        ans2+=a;
      dp[i]=a;
      if(i && dp[i-1]>0)
        dp[i]+=dp[i-1];
      if(dp[i]>ans1)
        ans1=dp[i];
    }
    if(ans1==0)
      ans1=max;
    if(ans2==0)
      ans2=max;
    printf("%lld %lld\n",ans1,ans2);
  }
  return 0;
}








In Pyhton3 :





# your code goes here
test = int(input())
while test:
	test -= 1
	input()
	num_list = [int(x) for x in input().split()]
	max_sum = 0
	tmp_sum = 0
	max_non_contg = 0
	flg = False
	mx = max(num_list)
	if mx < 0:
		print(str(mx) + " " + str(mx))
		continue
	for i in range(len(num_list)):
		if tmp_sum < 0:
			tmp_sum = 0
		tmp_sum += num_list[i]
		if tmp_sum > max_sum:
			max_sum = tmp_sum
		if num_list[i] > 0:
			max_non_contg += num_list[i]
	print(str(max_sum) + " " + str(max_non_contg))