HackerRank: The Maximum Subarray
private static void findMaxSumSubArray(short[] arr) {
long maxConSum = Long.MIN_VALUE, maxNonConSum = Long.MIN_VALUE, prevSum = 0;
for(short x: arr) {
int currentSum = x;
if(prevSum > 0) {
currentSum += prevSum;
}
if(currentSum > maxConSum) {
maxConSum = currentSum;
}
prevSum = currentSum;
if ( maxNonConSum < 0 && x > maxNonConSum) {
maxNonConSum = x;
} else if( maxNonConSum > 0 && x > 0) {
maxNonConSum += x;
}
}
System.out.println(maxConSum + " " + maxNonConSum);
}
def main(args: Array[String]) {
var scan = new Scanner(System.in);
var n = scan.nextInt();
for( i <- 1 to n ){
var size = scan.nextInt();
var numArray = new Array[Int](size);
for( j <- 0 to (size-1)){
numArray(j)=scan.nextInt();
}
printMax( numArray);
}
}
def printMax(nums: Array[Int]){
var max = 0;
var gen = 0;
var max_so_far = Integer.MIN_VALUE;
var all_neg=true;
var max_ele=Integer.MIN_VALUE;
for (i <- 0 until nums.length ) {
max += nums(i);
if (nums(i) > 0) {
gen += nums(i);
all_neg=false;
}
if(max_ele < nums(i) ){
max_ele=nums(i);
}
if (max < 0) {
max = 0;
}
if (max > max_so_far) {
max_so_far = max;
}
}
if(all_neg){
gen= max_ele;
max_so_far=max_ele;
}
System.out.println(max_so_far+"\t"+gen);// << max_so_far << "\t" << gen<<endl;
}
object Solution extends App {
val sc = new Scanner(System.in)
val out = new PrintWriter(System.out)
def solve(): List[Long] = {
val N = sc.nextInt
val A = List.fill(N)(sc.nextLong)
def cont(): Long = {
@tailrec
def loop(res: Long, acc: Long, xs: List[Long]): Long =
xs match {
case Nil =>
res
case h :: t =>
val y = (acc + h) max 0
loop(y max res, y, t)
}
loop(0, 0, A)
}
def nonCont(): Long = A.filter(_ > 0).sum
if (A.forall(_ < 0)) List.fill(2)(A.max)
else List(cont, nonCont)
}
for (_ <- 0 until sc.nextInt)
out.println(solve.mkString(" "))
out.flush
}
Given an array A={a1,a2,…,aN} of N elements, find the maximum possible sum of a
- Contiguous subarray
- Non-contiguous (not necessarily contiguous) subarray.
Empty subarrays should not be considered.
https://codepair.hackerrank.com/paper/Wz4rBXmv?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9private static void findMaxSumSubArray(short[] arr) {
long maxConSum = Long.MIN_VALUE, maxNonConSum = Long.MIN_VALUE, prevSum = 0;
for(short x: arr) {
int currentSum = x;
if(prevSum > 0) {
currentSum += prevSum;
}
if(currentSum > maxConSum) {
maxConSum = currentSum;
}
prevSum = currentSum;
if ( maxNonConSum < 0 && x > maxNonConSum) {
maxNonConSum = x;
} else if( maxNonConSum > 0 && x > 0) {
maxNonConSum += x;
}
}
System.out.println(maxConSum + " " + maxNonConSum);
}
def main(args: Array[String]) {
var scan = new Scanner(System.in);
var n = scan.nextInt();
for( i <- 1 to n ){
var size = scan.nextInt();
var numArray = new Array[Int](size);
for( j <- 0 to (size-1)){
numArray(j)=scan.nextInt();
}
printMax( numArray);
}
}
def printMax(nums: Array[Int]){
var max = 0;
var gen = 0;
var max_so_far = Integer.MIN_VALUE;
var all_neg=true;
var max_ele=Integer.MIN_VALUE;
for (i <- 0 until nums.length ) {
max += nums(i);
if (nums(i) > 0) {
gen += nums(i);
all_neg=false;
}
if(max_ele < nums(i) ){
max_ele=nums(i);
}
if (max < 0) {
max = 0;
}
if (max > max_so_far) {
max_so_far = max;
}
}
if(all_neg){
gen= max_ele;
max_so_far=max_ele;
}
System.out.println(max_so_far+"\t"+gen);// << max_so_far << "\t" << gen<<endl;
}
object Solution extends App {
val sc = new Scanner(System.in)
val out = new PrintWriter(System.out)
def solve(): List[Long] = {
val N = sc.nextInt
val A = List.fill(N)(sc.nextLong)
def cont(): Long = {
@tailrec
def loop(res: Long, acc: Long, xs: List[Long]): Long =
xs match {
case Nil =>
res
case h :: t =>
val y = (acc + h) max 0
loop(y max res, y, t)
}
loop(0, 0, A)
}
def nonCont(): Long = A.filter(_ > 0).sum
if (A.forall(_ < 0)) List.fill(2)(A.max)
else List(cont, nonCont)
}
for (_ <- 0 until sc.nextInt)
out.println(solve.mkString(" "))
out.flush
}