HackerRank The Maximum Subarray problem solution

In this HackerRank The Maximum Subarray problem solution we have given an array and we need to find the maximum possible sum among all nonempty subarrays and all nonempty subsequences and then print the two values as space-separated integers on one line.

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))

{"mode":"full","isActive":false}

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

{"mode":"full","isActive":false}

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

{"mode":"full","isActive":false}

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 %d\n",max_end,sum_non);
    }
    return 0;
}

{"mode":"full","isActive":false}