Created
September 20, 2013 12:16
-
-
Save anonymous/6636600 to your computer and use it in GitHub Desktop.
java project kadane's algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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