Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank The Maximum Subarray Problem Solution

HackerRank The Maximum Subarray Solution

Posted on June 21, 2023June 21, 2023 By Yashwant Parihar No Comments on 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:

  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.

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
HackerRank The Maximum Subarray Problem Solution

Table of Contents

  • The Maximum Subarray C Solution
  • The Maximum Subarray C++ Solution
  • The Maximum Subarray C Sharp Solution
  • The Maximum Subarray Java Solution
  • The Maximum Subarray JavaScript Solution
  • The Maximum Subarray Python 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 Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Fair Cut Problem Solution
Next Post: HackerRank Angry Children 2 Problem Solution

Related Posts

HackerRank Shashank and the Palindromic Strings Problem Solution HackerRank Shashank and the Palindromic Strings c
HackerRank Computer Game Problem Solution HackerRank Computer Game Problem Solution c
HackerRank Abbreviation Problem Solution HackerRank Abbreviation Problem Solution c
HackerRank Minimum MST Graph Problem Solution HackerRank Minimum MST Graph Solution c
HackerRank Going to the Office Problem Solution HackerRank Going to the Office Problem Solution c
HackerRank Marc's Cakewalk Problem Solution HackerRank Marc’s Cakewalk Problem Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme