HackerRank The Maximum Subarray Solution

In this post, we will solve 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:

all nonempty subarrays.
all nonempty subsequences.

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

Note that empty subarrays/subsequences should not be considered.

Example
arr = [1, 2, 3, 4, 5, 10] The maximum subarray sum is comprised of elements at inidices [1-5]. Their sum is 2+3+4+5+ 10 = 16. The maximum subsequence sum is comprised of elements at indices [1, 2, 4, 5] and their sum is 2+3+5+10=20.

unction Description

Complete the maxSubarray function in the editor below.

maxSubarray has the following parameter(s):

int arr[n]: an array of integers

Returns

int[2]: the maximum subarray and subsequence sums

Input Format

The first line of input contains a single integer t, the number of test cases.

The first line of each test case contains a single integer n.
The second line contains n space-separated integers arr[i] where 0 < i < n.

Sample Input 0

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

Sample Output 0

10 10
10 11

Explanation 0
In the first case: The maximum sum for both types of subsequences is just the sum of all the elements since they are all positive. In the second case: The subarray [2, -1, 2, 3, 4] is the subarray with the maximum sum, and [2, 2, 3, 4] is the subsequence with the maximum sum.

Sample Input 1

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

Sample Output 1

-1 -1

Explanation 1

Since all of the numbers are negative, both the maximum subarray and maximum subsequence sums are made up of one element, -1.

HackerRank The Maximum Subarray Problem Solution

The Maximum Subarray C Solution

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

int main() {
    int t,i,n,val,flag;
    int sum=0,min,sum1=0,bestsum=0;
    scanf("%d",&t);
    while(t--)
        {
        sum=0;sum1=0;flag=0;
        scanf("%d",&n);
        int a[n];
        for(i=0;i<n;i++)
            {
            
            scanf("%d",&a[i]);
            
            if(i==0)
                {
                bestsum=a[i];
                min=a[i];}
            if(a[i]>0)
                {
                sum1=sum1+a[i];
                if(a[i]>min)
                min=a[i];
            }
            val=sum+a[i];
            if(val>0)
                {
                sum=sum+a[i];
            }
            else
                {
                sum=0;
            }
            if(val>bestsum)
             bestsum=val;   
        }
        if(sum1==0)
            sum1=min;
        printf("%d %d\n",bestsum,sum1);
    }
    return 0;
}

The Maximum Subarray C++ Solution

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

int maxSubarray(int arr[],int n)
{
	int currMax = 0;
	int tillMax = 0;
	
	for(int i=0;i<n;i++)
	{
		currMax = currMax + arr[i];
		if(currMax<0)
		currMax = 0;
		else
		{
			if(tillMax<currMax)
			tillMax = currMax;
		}
	}
	return tillMax;
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int t,n;
    cin>>t;
    while(t--)
        {
        cin>>n;
        int arr[n];
        int arr2[n];
        for(int i=0;i<n;++i)
        {
        	cin>>arr[i];
        	arr2[i] = arr[i];
		}
        
        sort(arr2, arr2+n);
        
        int negMax=0;
        for(int i=n-1;i>=0;--i)
        {
            if(arr2[i]<0)
            {
            	negMax = arr2[i];
            	break;
			}
		}
        
        
        int temp1 = 0; //non contiguous
        int cnt = 0;
        bool isDone = true;
         for(int i=0;i<n;++i)
             {
             if(arr[i]>=0)
                 {
                  temp1 = temp1 + arr[i];
                 cnt++;
             }
         }
         int c;
         if(cnt>0)
         c = maxSubarray(arr,n);
         
        if(cnt>0)
        cout<<c<<" "<<temp1<<endl;
        else
            {
            if(cnt==0)
                cout<<negMax<<" "<<negMax<<endl;
        }
    }
    return 0;
}

The Maximum Subarray C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        int cnt = Convert.ToInt32(Console.ReadLine());
        
        for(var k = 0; k < cnt; k++){
            int size = Convert.ToInt32(Console.ReadLine());
            List<int> data = new List<int>();
            foreach(var d in Console.ReadLine().Split()){
                data.Add(Convert.ToInt32(d));
            }
            
            bool allNegative = true;
            int sum = 0;
            int max = Int32.MinValue;
            int current = 0;
            int best = Int32.MinValue;
            for(var i = 0; i < size; i++){
                if(data[i] >= 0){
                    sum += data[i];
                    allNegative = false;
                }
                max = data[i] > max ? data[i] : max;
                
                current += data[i];
                if(current < 0){
                    current = 0;
                }
                
                best = current > best ? current : best;
            }
            
            if(allNegative){
                Console.WriteLine(max + " " + max);
            }
            else{
                Console.WriteLine(best + " " + sum);
            }
        }
    }
}

The Maximum Subarray Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'maxSubarray' function below.
     *
     * The function is expected to return an INTEGER_ARRAY.
     * The function accepts INTEGER_ARRAY arr as parameter.
     */

    public static List<Integer> maxSubarray(List<Integer> arr) {
    int subarrayMax = kadaneSubArray(arr);
        int subSubmax = kadaneSubSeq(arr);
        return List.of(subarrayMax,subSubmax);
    }
    static int kadaneSubSeq(List<Integer> A){
        int sum = 0;
        int min = Integer.MIN_VALUE;
        for(var a : A) {
            sum += a > 0 ? a : 0;
            if(a < 0)
                min = Math.max(min,a);
        }

        return sum == 0 ? min : sum;
    }
    static private int kadaneSubArray(List<Integer> arr){
        int max = arr.get(0);
        int curMax = arr.get(0);
        for(int i = 1;i<arr.size();++i){
            curMax = Math.max(curMax + arr.get(i),arr.get(i));
            max = Math.max(max,curMax);
        }
        return max;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, t).forEach(tItr -> {
            try {
                int n = Integer.parseInt(bufferedReader.readLine().trim());

                List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                    .map(Integer::parseInt)
                    .collect(toList());

                List<Integer> result = Result.maxSubarray(arr);

                bufferedWriter.write(
                    result.stream()
                        .map(Object::toString)
                        .collect(joining(" "))
                    + "\n"
                );
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

The Maximum Subarray JavaScript Solution

function findMaximumSums(array){
    var localMax = 0;
    var globalMax = 0;
    var sumPositives = 0;
    for(var i in array){
        if(array[i] > 0){
            sumPositives += array[i];
        }
        localMax += array[i];
        globalMax = localMax > globalMax? localMax: globalMax;
        if(localMax < 0){ localMax = 0; }
    }
    if(globalMax === 0 ){
        globalMax = array[0];
        sumPositives = array[0];
    }
    console.log(globalMax, sumPositives);
}

function processData(input) {
    var array = input.split('\n').slice(1);
    for(var i = 1; i < array.length; i+=2){
        var testData = array[i].split(' ').map(function(n){ return parseInt(n); })
        findMaximumSums(testData);
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

The Maximum Subarray Python Solution

t = int(input())
for _ in range(t):
    n = int(input())
    l = list(map(int,input().strip().split()))
    ans1 = l[:1]
    mx = l[0]
    for k in range(1,n):
        if ans1[-1] >=0 :
            ans1.append(ans1[-1]+l[k])
        else:
            ans1[-1] = l[k]
        mx = max(mx,ans1[-1])
    ans2 = sum([x for x in l if x>0])
    if ans2 == 0:
        ans2 = max(l)
    print(mx,ans2)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python