Table of Contents
The Maximum Subarray – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
1 Month Preparation Kit Solutions – HackerRank
C++ The Maximum Subarray HackerRank Solution
#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;
}
}
Java The Maximum Subarray HackerRank Solution
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) );
}
}
}
Python 3 The Maximum Subarray HackerRank Solution
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))
JavaScript The Maximum Subarray HackerRank Solution
C The Maximum Subarray HackerRank Solution
#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}
Leave a comment below
