Skip to content
Programming101
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programmingoneonone

HackerRank The Maximum Subarray problem solution

YASH PAL, 31 July 2024

In this HackerRank The Maximum Subarray problem solution we have given an array and we need to find the maximum possible sum among all nonempty subarrays and all nonempty subsequences and then print the two values as space-separated integers on one line.

HackerRank The Maximum Subarray problem solution

Problem solution in Python.

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

{“mode”:”full”,”isActive”:false}

Problem solution in Java.

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) );
        }
    }
}

{“mode”:”full”,”isActive”:false}

Problem solution in C++.

#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;
    }
}

{“mode”:”full”,”isActive”:false}

Problem solution in C.

#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 %dn",max_end,sum_non);
    }
    return 0;
}

{“mode”:”full”,”isActive”:false}

Algorithms coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes