HackerRank The Maximum Subarray problem solution

In this HackerRank The Maximum Subarray problem solution, We define subsequence as any subset of an array. We define a subarray as a contiguous subsequence in an array.

Given an array, find the maximum possible sum among:

1. all nonempty subarrays.
2. all nonempty subsequences.

Print the two values as space-separated integers on one line.

Note that empty subarrays/subsequences should not be considered.

Function Description

Complete the maxSubarray function in the editor below.

maxSubarray has the following parameter(s):

• int arr[n]: an array of integers

HackerRank The Maximum Subarray problem solution in Python.

def max_subarray(A):

    positive_sum = 0
    if (A[0] > 0):
        positive_sum = A[0]
        
    largest_num = A[0]
    
    max_ending_here = max_so_far = A[0]

    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)

        if (x > largest_num):
            largest_num = x
        if (x > 0):
            positive_sum += x

    if (largest_num < 0):
        non_contingent_sum = largest_num
    else:
        non_contingent_sum = positive_sum
    return max_so_far, non_contingent_sum

    
inputs = input()
for i in range(0,int(inputs)):
    input() # number of elements - not needed
    elements = input()
    arr = [int(x) for x in elements.strip().split(" ")]
    max1, max2 = max_subarray(arr)
    print ("{:d} {:d}".format(max1, max2))

The Maximum Subarray problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    public static int contigousSum(int[] arr){
        int max_sum =arr[0];
        int temp_sum=arr[0];
        for(int i=1; i<arr.length; i++){
            temp_sum += arr[i];
            if(temp_sum > max_sum) max_sum = temp_sum;
            else{
                if(temp_sum < 0)
                temp_sum = 0;
            }
        }
        return max_sum;
    }
    public static int s(int[] arr, int j){
        if(j==0)   return arr[j];
        return Math.max(s(arr,j-1), Math.max(arr[j], s(arr,j-1) +arr[j]));
    }
    
    
    public static int sequenceSum(int[] arr){
        int length = arr.length;
      //  return s(arr, length-1); 
        int sums[] = new int[length];
        sums[0] = arr[0];
        for(int i=1; i < arr.length; i++){
            sums[i] = Math.max(sums[i-1], Math.max(arr[i], sums[i-1] +arr[i]));
        }
        return sums[length-1]; 
    }
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        for(int i = 0; i < t; i++){
            int l = scan.nextInt();
            int arr[] = new int[l];
            for(int j = 0; j<l; j++){
                arr[j] = scan.nextInt();
            }
            System.out.println(contigousSum(arr)+ " "+ sequenceSum(arr) );
        }
    }
}

Problem solution in C++.

#include <iostream>

using namespace std;
#define MAXN 100003
#define ninf -10000000000
int T,N;
int A[MAXN];
long long maxSumCont, maxSumNonCont;

int main()
{
    cin>>T;
    while(T--) {
        cin>>N;
        maxSumNonCont = 0;
        maxSumCont = ninf;
        int maxNum = ninf;
        long long tempSum = 0;
        for(int i = 0; i < N; i++) {
            cin>>A[i];
            if(A[i] > 0)
                maxSumNonCont += A[i];
            maxNum = max(maxNum, A[i]);
            if(tempSum < 0){
                tempSum = 0;
            }
            tempSum += A[i];
            if(maxSumCont < tempSum)
                maxSumCont = tempSum;

        }
        if(maxNum < 0)
            maxSumNonCont = maxNum;
        cout<<maxSumCont<<' '<<maxSumNonCont<<endl;
    }
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int test,n,i,a,max_end,sum_non,sum_contigues,flag,max;
    scanf("%d",&test);
    while(test--)
        {
        scanf("%d",&n);
        sum_non=0;sum_contigues=0;max_end=0;flag=0,max=-123456;
        for(i=0;i<n;i++)
            {
            scanf("%d",&a);
            if(max<a)
                max=a;
            if(a==0)
                flag=1;
            if(a>0)
                {
                sum_non+=a;
            }
            sum_contigues+=a;
            if(sum_contigues<0)
                sum_contigues=0;
            if(sum_contigues>max_end)
                max_end=sum_contigues;
        }
        if(!flag&&sum_non==0)
            {
            max_end=max;
            sum_non=max_end;
        }
        printf("%d %dn",max_end,sum_non);
    }
    return 0;
}