/*
* Author: Son Pham
* Date: March 5, 2013
* Purpose: To help Jill.
* Problem: 507 - Jill Rides Again
* Comment: Good for you Jill, good for you...
* It's not the greatest looking code because it's midterm week.
* I might clean it up when tests are over.
*/
import java.util.Scanner;
public class JillRidesAgain {
private static int[] stops = new int[20000];
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int routes = reader.nextInt();
int index = 1;
while(index <= routes){
int numStops = reader.nextInt() - 1;
for(int i = 0; i < numStops; i++){
stops[i] = reader.nextInt();
}
subMaxSum(stops, numStops, index);
index++;
}
}
public static void subMaxSum(int[] a, int n, int r){
int maxI = 0;
int maxJ = 0;
int i = 0;
int j = 0;
int currSum = a[i];
int maxSum = currSum;
while(j < n){
if( i==j )
currSum = a[j];
else
currSum += a[j];
if(currSum < 0){
i = j+1;
currSum = 0;
}
else if (currSum >= maxSum){
int lcr = maxJ - maxI;
if((currSum == maxSum)&&((j-i) > lcr)){
maxI = i;
maxJ = j;
maxSum = currSum;
}
else if(currSum > maxSum){
maxI = i;
maxJ = j;
maxSum = currSum;
}
}
j++;
}
//System.out.println(a[maxI]+" "+a[maxJ]+" "+currSum);
if(maxSum <= 0)
System.out.println("Route "+r+" has no nice parts");
else{
maxI+=1;
maxJ+=2;
System.out.printf("The nicest part of route "+r+" is between stops"
+ " %d and %d\n",maxI,maxJ);
}
}
}
The statements and opinions included in these pages are those of only. Any statements and
opinions included in these pages are not those of Louisiana
State University or the LSU Board of Supervisors.
© 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015