Hackerrank – Problem Statement
A description of the problem can be found on Hackerrank.
Solution
- Contiguous sum – using Kadane’s algorithm
- Non-contiguous sum – filter all positive elements from given array and sum them. If this array is empty. Take the greatest element.
I created solution in:
All solutions are also available on my GitHub.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
import java.util.*; public class MaxSubarray { public static void main(String[] args) { Scanner stdin = new Scanner(System.in); int tests = stdin.nextInt(); for(int i = 0; i < tests; i++) { int elementCount = stdin.nextInt(); int[] arr = new int[elementCount]; for(int j = 0; j < elementCount; j++) { arr[j] = stdin.nextInt(); } int contiguousSum = kadane(arr); int nonContiguousSum; if(hasPositiveElement(arr)) { nonContiguousSum = sumPositiveElement(arr); } else { nonContiguousSum = max(arr); } System.out.println(contiguousSum + " " + nonContiguousSum); } stdin.close(); } private static int kadane(int[] arr) { int maxSoFar = arr[0]; int maxEndings = arr[0]; for(int j = 1; j < arr.length; j++) { int el = arr[j]; maxEndings = Math.max(el, maxEndings + el); maxSoFar = Math.max(maxSoFar, maxEndings); } return maxSoFar; } private static boolean hasPositiveElement(int[] arr) { for(int j = 0; j < arr.length; j++) { if(arr[j] > 0) { return true; } } return false; } private static int sumPositiveElement(int[] arr) { int sum = 0; for(int j = 0; j < arr.length; j++) { if(arr[j] > 0) { sum += arr[j]; } } return sum; } private static int max(int[] arr) { int max = Integer.MIN_VALUE; for(int j = 0; j < arr.length; j++) { if(arr[j] > max) { max = arr[j]; } } return max; } } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
'use strict'; const _ = require('lodash'); const processData = input => { const lines = input.split('\n'); let index = 0; const tests = parseInt(lines[index++]); for(let i = 0; i < tests; i++) { const elementCount = lines[index++]; const arr = lines[index++].split(' ').map(el => parseInt(el)); const contiguousSum = kadane(arr); const positiveNumbers = arr.filter(el => el > 0); let nonContiguousSum; if(positiveNumbers.length === 0) { nonContiguousSum = _.max(arr); } else { nonContiguousSum = _.sum(positiveNumbers); } console.log(contiguousSum + ' ' + nonContiguousSum); } }; const kadane = arr => { let maxSoFar = arr[0]; let maxEndings = arr[0]; arr.slice(1, arr.length).forEach(el => { maxEndings = Math.max(el, maxEndings + el); maxSoFar = Math.max(maxSoFar, maxEndings); }); return maxSoFar; }; process.stdin.resume(); process.stdin.setEncoding("ascii"); let _input = ""; process.stdin.on("data", input => _input += input); process.stdin.on("end", () => processData(_input)); |
Scala
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
import scala.io.Source object MaxSubarray extends App { val lines = Source.stdin.getLines.drop(1).toList val arrayLines = lines.grouped(2).map(group => group.toList(1)) val arrays = arrayLines.map(_.split(" ").map(_.toInt)) arrays.foreach { arr => { val contiguousSum = kadane(arr) val positiveNumbers = arr.filter(_ > 0) val nonContiguousSum = if(positiveNumbers.isEmpty) arr.max else positiveNumbers.sum println(contiguousSum + " " + nonContiguousSum) } } def kadane(arr: Array[Int]): Int = { var maxSoFar = arr(0) var maxEndings = arr(0) arr.slice(1, arr.length).foreach(el => { maxEndings = scala.math.max(el, maxEndings + el) maxSoFar = scala.math.max(maxSoFar, maxEndings) }) maxSoFar } } |
Ruby
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
def kadane(arr) maxSoFar = arr[0] maxEndings = arr[0] arr.each do |el| maxEndings = [el, maxEndings + el].max maxSoFar = [maxSoFar, maxEndings].max end maxSoFar end tests = gets.to_i tests.times do |i| n = gets.to_i arr = gets.split.map{ |i| i.to_i} contiguous_sum = kadane(arr) positive_numbers = arr.select { |el| el > 0} non_contiguous_sum = 0 if(positive_numbers.size == 0) non_contiguous_sum = arr.max else positive_numbers.each {|el| non_contiguous_sum += el} end puts "#{contiguous_sum} #{non_contiguous_sum}" end |
I think your kadane implementation is not correct, instead of array position , the maxsofar and the maxEnding should rather be set to zero.
Hi.
If you look at the wikipedia page there are two Kadane algorithms. I chose the second, which sets
maxSoFarandmaxEndingto first element of the array. There is a test case in Hackerrank that all elements are negative and if you setmaxSoFarandmaxEndingto0you will get wrong result.