Hackerrank - The Maximum Subarray

Hackerrank – Popis problému

Celý popis zadania sa nacháza – Hackerrank.

Riešenie

Contiguous sum – použitie Kadane-ovho algoritmu
Non-contiguous sum – vybraž len všetky kladná prvky zo zadaného poľa. V prípade, že takého pole je prázdne, výsledok je najväčšie číslo zo zadaného poľa.

Vytvoril som riešenie v týchto programovacích jazykoch:

Scala
Java
JavaScript
Ruby

Všetky riešenia sú dostupné aj na mojom GitHub profile.

Java

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

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

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

'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

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

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

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

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

Pavol Pidanič

Dokážem na 10 prstoch napočítať do 1023

Hackerrank – The Maximum Subarray

Hackerrank – Popis problému

Riešenie

Java

JavaScript

Scala

Ruby

Leave a Reply Cancel reply