Skip to content

Instantly share code, notes, and snippets.

Created September 20, 2013 12:16
Show Gist options
  • Save anonymous/6636600 to your computer and use it in GitHub Desktop.
Save anonymous/6636600 to your computer and use it in GitHub Desktop.
java project kadane's algorithm
package proj1.main;
import java.io.File ;
import java.io.FileNotFoundException ;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Scanner ;
import java.util.ArrayList ;
public class Project
{
public static void main(String[] args)
{
String arraySize ;
float[] numbers ;
int arrayPos = 0 ; //used later for adding numbers into array.
Scanner scanner ;
try {
if(args[0].matches("vector\\d++.txt")) {
scanner = new Scanner(new File(args[0]));
arraySize = args[0].substring(6,args[0].length() - 4) ;
//The previous line extracts the number in the filename.
//pos 6 in the filename string is the start of the number as "vector" is
//6 chars long. The 2nd argument to the substring method is
//args[0].length() - 4 because the filename ends in ".txt" after the number
//which is 4 chars long. Thus the substring call cuts out the number away
//from everything else.
numbers = new float[Integer.parseInt(arraySize)] ;
scanner.useDelimiter(",") ;
while(scanner.hasNext() == true) {
try{
numbers[arrayPos] = (float) scanner.nextDouble() ;
} catch(InputMismatchException ex) {
scanner.close() ;
break ;
}
arrayPos++ ;
}
findMaxSubvector(numbers) ;
} else {
System.out.println("Usage: java Project filename \n where filename is in the format " +
"\"vectorX.txt\", X being a number") ;
System.exit(0) ;
}
} catch (FileNotFoundException e) { //In the event the filename is valid but no such file is
//found, avoid a crash due to thrown FileNotFoundException
System.out.println("File not found.") ;
System.out.println(args[0]) ;
}
}
public static void findMaxSubvector(float[] array)
{
float maxSubvector = Float.MIN_VALUE, cumulativeSum = 0 ;
int maxStartIndex = 0, maxEndIndex = 0, maxStartIndexUntilNow = 0 ;
//TODO implement Kadane's algorithm
for(int i = 0 ; i < array.length ; i++) {
cumulativeSum += array[i] ;
if(cumulativeSum > maxSubvector) {
maxSubvector = cumulativeSum ;
maxStartIndex = maxStartIndexUntilNow ;
maxEndIndex = i ;
} else if(cumulativeSum < 0) {
maxStartIndexUntilNow = i + 1 ;
cumulativeSum = 0 ;
}
}
System.out.println("Max subvector: " + maxSubvector) ;
System.out.println("Start index: " + maxStartIndex) ;
System.out.println("End index: " + maxEndIndex) ;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment