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