0

私は codeeval.com の問題に取り組んでいます - http://codeeval.com/open_challenges/17/。「リスト内の連続する整数の最大和を求めるプログラムを書いてください」.

入力は、コンマ区切りの整数のリストを含むテキスト ファイルで、1 行に 1 つずつ入力されます。

-10、2、3、-2、0、5、-15

2,3,-2,-1,10

その入力は、最初の行で 8 を生成し、2 番目の行で 12 を生成する必要があります。私の答えは以下のとおりですが、2 行目で 12 を取得する方法がわかりません。そのため、私の質問は主に何が欠けているのかということです。求められているものを誤解していますか? (答えは 13 です)

注意 - 私はアイルランドに住んでいるので、これは純粋に私自身の経験のためです。あなたは私の求職活動を手伝ってくれるわけではありません! また、ここで同様の質問をすべて調べましたが、関連するものは見つかりませんでした。

質問の私の解釈が間違っている場合、必要なのは正しい方向へのポイントだけであり、必ずしもコードではありません。(同様に、誰かが 2 行目が 13 ではなく 12 に評価される方法を指摘できますか)

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);
    }
}
4

4 に答える 4

5

Kadane のアルゴリズムを見てみることをお勧めします。

編集: @Paolo と @Vlad が指摘したように、シーケンスを探すのではなく、最大の 2 つの数値を追加しているため、正しい結果が得られません。Kadane のアルゴリズムは、最初にデータ セット内の各位置で終わる最大の合計を見つけることによって、シーケンスの最大の合計を見つけます。

于 2012-09-04T10:17:49.623 に答える
2

問題は、連続する整数の最大和を求めることです。あなたのプログラムは、最大のものと 2 番目に大きいものを選んでそれらを足し合わせているのであって、同じことではありません。

最初の行では、サブシーケンスを取ることによって最大の合計が達成されます。

2, 3, -2, 0, 5

これは合計で 8 になります (2 と -2 が相殺され、実質的に最大の数値と 2 番目に大きい数値が残るという事実は危険です)。

2 行目では、シーケンス全体を取得することによって最大の合計が得られます。

2 + 3 + -2 + -1 + 10

合計すると 12 になります。

于 2012-09-04T10:23:46.100 に答える
0 
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-06T14:14:16.293 に答える
0

以下のアルゴリズムでコードを変更しました。基本的に私が理解していれば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-04T10:46:51.283 に答える