HackerRank The Maximum Subarray Solution Yashwant Parihar, June 21, 2023August 1, 2024 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. Examplearr = [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 0In 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 CcppCSharpHackerrank Solutionsjavajavascriptpython