確定列表中連續整數的最大總和java

我正在解決codeeval.com上的問題 - http://codeeval.com/open_challenges/17/。「編寫一個程序來確定列表中連續整數的最大總和」。確定列表中連續整數的最大總和java

輸入是一個包含逗號分隔的整數列表的文本文件，每行一個例如

-10，2，3，-2，0，5，-15

2,3，-2，-1,10

即輸入應產生8對第一行和12爲第二。我的答案在下面，但我看不到第二行如何得到12，所以我的問題主要是我錯過了什麼，我是否誤解了要求的內容？（我得到13的答案）

N.B. - 我住在愛爾蘭，所以這純粹是爲了我自己的經歷，你不會幫助我申請工作！另外，我在這裏經歷了所有類似的問題，並且找不到任何相關的問題。

如果我對問題的解釋不正確，我所需要的只是一個正確方向的點，不一定是代碼。（如，能有人指出，第二行如何評估以12和13不會）

import java.util.*; 
import java.io.*; 

public class largest_sum { 

    public static void main(String[] args) throws Exception { 

     FileReader input = new FileReader(args[0]); 
     BufferedReader bufRead = new BufferedReader(input); 
     String line; 

     line = bufRead.readLine(); 

     while(line != null) { 
      addInts(line); 
      line = bufRead.readLine(); 
     } 
     bufRead.close(); 
     System.exit(0); 
    } 

    public static void addInts(String line) { 
     String[] numbers = line.split(","); 
     Integer largest = Integer.parseInt(numbers[0].trim()); 
     Integer secondLargest = 0; 
     for(String s : numbers) { 
      Integer converted = Integer.parseInt(s.trim()); 
      if(converted > largest) { 

       secondLargest = largest; 
       largest = converted; 
      } 
     } 
     System.out.println(largest + secondLargest); 
    } 
}

來源

2012-09-04 Saf

「我住在愛爾蘭所以這純粹是爲了我自己的經驗，你會不會幫助我工作申請」 - 生活在愛爾蘭與它有什麼關係？ –

因爲對於在美國工作的人來說這是一份工作的挑戰...... 我只是爲了體驗而努力。不是工作申請。 – Saf

你的錯誤是你正在添加序列中最大的兩個數字。但他們不一定是連續的！在考慮的情況下，序列「3,10」不是解決問題的方法，但是它是由您的算法選擇的。有關如何解決問題的描述，請參閱@ mtsvetkov的答案。 – Vlad

我建議在看看Kadane's algorithm。

編輯：正如@Paolo和@Vlad指出的那樣 - 您沒有得到正確的結果，因爲您正在添加最大的兩個數字，而不是查找序列。 Kadane的算法首先找到數據集中每個位置的最大和，然後找到序列的最大和。

來源

2012-09-04 10:17:49 mtsvetkov

該算法的快速谷歌立即解決了這個問題。現在我只需要確保我理解它，非常有趣，謝謝。 – Saf

問題是要求找到最大的總和連續的整數。你的計劃是挑選最大和次大的並將它們加在一起，而不是相同的東西。

在第一行中，最大的總和通過採取subseqence來達到的：

2, 3, -2, 0, 5

其總計爲8（一個事實，即2和-2抵消你留下有效的最大+第二大數字是紅鯡魚）。

在第二行中的最大總和由取整個序列來達到的：

2 + 3 + -2 + -1 + 10

其總計爲12

來源

2012-09-04 10:23:46 Paolo

謝謝澄清，如果我能讓兩個問題成爲我的答案！無論如何給它+1。 – Saf

我與以下算法修改的代碼。基本上，如果我已經明白correctly it is like find valid integer on the right side then move to left side and find valid integer there then get the sum.

public static void main(String[] args) throws Exception { 

    addInts("-10,2,3,-2,0,5,-15"); 
    addInts("2,3,-2,-1,10"); 
} 

public static void addInts(String line) { 
    String[] numbers = line.split(","); 
    // First convert Strings to integer array 

    int[] ints = new int[numbers.length]; 
    int count = 0; 

    for (String number : numbers) { 
     ints[count++] = Integer.parseInt(number); 
    } 

    // now find first valid and last valid 

    int firstValidIndex = -1; 
    int lastValidIndex = -1; 
    for (count = 0;;) { 
     if (ints[count] < 0 && firstValidIndex == -1) { 
      count++; 
      continue; 
     } else { 
      if (firstValidIndex == -1) { 
       firstValidIndex = count; 
       //Swap the loop here now we have to find backwards    
       count = ints.length - 1; 
      } else { 
       if (ints[count] < 0) { 
        count--; 
        continue; 
       } else { 
        lastValidIndex = count; 
        break; 
       } 

      } 

     } 
    } 

    // Calculate the sum now 
    int sum = 0; 
    for (count = firstValidIndex; count <= lastValidIndex; count++) { 
     sum = sum + ints[count]; 
    } 

    System.out.println(sum); 
}

輸出

8 
12

來源

2012-09-04 10:46:51

不，我認爲這些數字算出來只是一個愉快的巧合，我認爲他們在投入和預期的答案中竭盡全力拋出紅鯡魚。正確的答案涉及應用Kadane的算法 - http://stackoverflow.com/questions/7233042/kadane-algorithm-in-java。請注意，我也沒有正確理解這個問題，因此在這裏發佈！ – Saf

package com.salpe.scjp.algo; 

public class Algo1 { 

    private static int[] test = new int[] { -10, 2, 3, -2, 0, 5, -15 }; 

    public static void main(String[] args) { 


     int highestSum = test[0]; 

     int higheststart = 0; 
     int highestend = 0; 

     for (int i = 0; i < test.length; i++) { 

      for (int j = 0; j < test.length; j++) { 
       if (i != j) { 
        System.out.print("[ " + i + ", " + j); 
        System.out.print(" = "+findSum(i, j) +"]"); 

        if(highestSum < findSum(i, j)){ 
         highestSum = findSum(i, j); 
         higheststart = i; 
         highestend = j; 
        } 
       } 

      } 

      System.out.println(""); 

     } 

     System.out.println("Highest Sum " +highestSum); 
     toString(higheststart, highestend); 

    } 

    public static int findSum(int i, int j) { 

     int sum =0; 

     for (int j2 = i; j2 <= j; j2++) { 

      sum = sum +test[j2]; 

     } 

     return sum; 
    } 


    public static int toString(int i, int j) { 

     int sum =0; 

     for (int j2 = i; j2 <= j; j2++) { 

      System.out.print(" ,"+test[j2]); 

     } 

     return sum; 
    } 

} 


---------- 

[ 0, 1 = -8][ 0, 2 = -5][ 0, 3 = -7][ 0, 4 = -7][ 0, 5 = -2][ 0, 6 = -17] 
[ 1, 0 = 0][ 1, 2 = 5][ 1, 3 = 3][ 1, 4 = 3][ 1, 5 = 8][ 1, 6 = -7] 
[ 2, 0 = 0][ 2, 1 = 0][ 2, 3 = 1][ 2, 4 = 1][ 2, 5 = 6][ 2, 6 = -9] 
[ 3, 0 = 0][ 3, 1 = 0][ 3, 2 = 0][ 3, 4 = -2][ 3, 5 = 3][ 3, 6 = -12] 
[ 4, 0 = 0][ 4, 1 = 0][ 4, 2 = 0][ 4, 3 = 0][ 4, 5 = 5][ 4, 6 = -10] 
[ 5, 0 = 0][ 5, 1 = 0][ 5, 2 = 0][ 5, 3 = 0][ 5, 4 = 0][ 5, 6 = -10] 
[ 6, 0 = 0][ 6, 1 = 0][ 6, 2 = 0][ 6, 3 = 0][ 6, 4 = 0][ 6, 5 = 0] 
Highest Sum 8 
,2 ,3 ,-2 ,0 ,5

來源

2012-12-06 14:14:16

確定列表中連續整數的最大總和java

回答

相關問題