jack
BAN USERimport java.util.ArrayList;
public class MaxSumVal {
public static void main(String[] args) {
Integer[] noArray = {-1,4,5,-2,-6,6};
//Integer[] noArray = {1,0,5,25,-1,4,5,-2,-6,6};
//Integer[] noArray = {-1,-9,-5,0,1,10,-3,5,12,-34};
//Integer[] noArray = {-1};
//Integer[] noArray = {-1,9};
Integer noArrayLen = noArray.length;
Integer finalSum = 0;
ArrayList<Integer> sumValues = new ArrayList<Integer>();
Integer tempVal = 0;
Integer iPlusOneAdjacency = 0;
if(noArrayLen == 1){
//If the number of the values is equal to 1 then the value itself will be the highest
finalSum = noArray[0];
sumValues.add( noArray[0] );
}else if(noArrayLen == 2){
//If the number of the values is equal to 2 then choose the greater value
finalSum = (noArray[0] > noArray[1]) ? noArray[0] : noArray[1];
sumValues.add( finalSum );
}else if(noArrayLen >= 3){
//If the number of the values is equal >= 3 then do the following
for(Integer i=0; i<noArrayLen; i=i+2 ){
//resetting tempVal at the beginning of each loop
tempVal = 0;
if(i-1 > 0 && noArray[i-1] < noArray[i]){
if(i+1 < noArrayLen && noArray[i] > noArray[i+1]){
tempVal = noArray[i];
//we need to check for adjacency only when we select value at i
if(iPlusOneAdjacency == i){
//if adjacency was set then we'll replace the previously set values
//to the current value and subtract that value from te finalSum
if(sumValues.size() > 0){
finalSum -= sumValues.get(sumValues.size() - 1);
sumValues.set(sumValues.size() - 1, tempVal);
iPlusOneAdjacency = 0;
}
}else{
sumValues.add( tempVal );
}
finalSum +=tempVal;
}else{
//An adjacency is always set if an i+1 values is selected
tempVal = noArray[i+1];
//we set the iPlusOneAdjacency value to i+2 as the next loop has the value = i+2
iPlusOneAdjacency = i + 2;
sumValues.add( tempVal );
finalSum += tempVal;
}
}else{
if(i+1 < noArrayLen && noArray[i] > noArray[i+1]){
if(i-1 >0){
tempVal = noArray[i-1];
if(iPlusOneAdjacency == 0){
sumValues.add( tempVal );
finalSum += tempVal;
}else{
iPlusOneAdjacency = 0;
}
}else{
tempVal = noArray[i];
sumValues.add( tempVal );
finalSum += tempVal;
}
}else{
tempVal = noArray[i+1];
iPlusOneAdjacency = i + 2;
sumValues.add( tempVal );
finalSum += tempVal;
}
}
}
}
System.out.println(finalSum);
System.out.println(sumValues);
}
}
The solution below is particularly tuned for just this problem (not generic), but serves the purpose for the mentioned problem. The solution i think is basically O(n-1).
public class TwoStep {
public static void main(String[] args) {
Integer[] numList = {5,2,1,5,3,4,5,6,5,5};
//we do numList.length-1 so that we don't get the array out of bounds exception when accessing the value at i+1
for(int i=0; i < numList.length-1 ; i++){
//We check if value at i == i+1
//or
// if i-1 >=0 and i-1 == i+1
//then i+1 should be the matched value
//since we know there is only one value that is going to be repeated
//we can break the loop at this point and print out the output
if((numList[i] == numList[i+1]) || (i-1 >= 0 && numList[i+1] == numList[i-1])){
System.out.println(numList[i+1]);
break;
}
}
}
}
This solution is O(m+n)
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashMap;
public class WordMaker {
public static void main(String[] args) {
// Defining local variables
String fileName = "wordList.txt";
char[] letterList = {'a','l','l','i','e','s','m'};
// Create a dictionary of the list of letters and their count
HashMap<Character, Integer> letterCount = new HashMap<Character, Integer>();
for(char l : letterList)
letterCount.put(l, letterCount.containsKey(l) ? letterCount.get(l) + 1 : 1);
// Read the file line by line to find the longest word
String line;
char[] lineChars;
Integer currlineLength;
Integer tempLongestWordLength=0;
ArrayList<String> currLongestWords = new ArrayList<String>();
HashMap<Character, Integer> tempLCount = new HashMap<Character, Integer>();
BufferedReader br;
try {
br = new BufferedReader(new FileReader(new File(fileName)));
while((line = br.readLine()) != null) {
//Storing the dictionary temporarily in tempLCount
tempLCount.putAll(letterCount);
//Reset currlineLength
currlineLength=0;
//don't go further if the current line length is shorter than the current longest word length
if(line.length() < tempLongestWordLength) continue;
//convert string to character array, so that we can loop through each letter
lineChars = line.toCharArray();
for(Character lc : lineChars){
//if the letterCount contains the key we move forward or we break this for loop and continue with the next line
if(!letterCount.containsKey(lc)) break;
//subtract from the available count of letters
tempLCount.put(lc,tempLCount.get(lc) - 1);
//if the count of the letter exceeds the count in the letter list then break this for loop
if(tempLCount.get(lc) < 0) break;
//increase the count of the letters that wen through
currlineLength++;
}
//If the count of the letters that went through is same as the length of the line string then there was a match
if(currlineLength == line.length()){
//If the current line length is greater than the longest word length then we clear the currLongestWord list
//and put this new one and change the longest length to the current line length
if(line.length() > tempLongestWordLength){
tempLongestWordLength = line.length();
currLongestWords.clear();
}
//Finally add the line to the currLongestWords list
currLongestWords.add(line);
}
}
} catch (Exception e) {
e.printStackTrace();
}
//Print out the list of longest words
System.out.println(currLongestWords);
}
}
- jack August 12, 2014