0

我正在处理 codeeval.com 上的一个问题 - http://codeeval.com/open_challenges/17/。“编写一个程序来确定列表中连续整数的最大和”。

输入是一个包含逗号分隔的整数列表的文本文件，每行一个，例如

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

2,3,-2,-1,10

该输入应为第一行生成 8，为第二行生成 12。我的答案在下面，但我看不到第二行如何获得 12，所以我的问题主要是我缺少什么，我是否误解了所要求的内容？（我得到 13 的答案）

注意 - 我住在爱尔兰，所以这纯粹是为了我自己的经验，你不会帮助我申请工作！此外，我在这里查看了所有类似的问题，但找不到任何相关内容。

如果我对问题的解释不正确，我所需要的只是指向正确的方向，而不一定是代码。（如，有人可以指出第二行如何计算为 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);
    }
}
4

4 回答 4

5

我建议看看Kadane 的算法。

编辑：正如@Paolo 和@Vlad 指出的那样 - 你没有得到正确的结果，因为你正在添加最大的两个数字，而不是寻找一个序列。Kadane 的算法通过首先找到在数据集中每个位置结束的最大和来找到序列的最大和。

于 2012-09-04T10:17:49.623 回答
2

问题是要求找到连续整数的最大和。您的程序正在选择最大的和第二大的并将它们加在一起，而不是一回事。

在第一行中，通过获取子序列来获得最大的总和：

2, 3, -2, 0, 5

总和为 8（事实上，2 和 -2 抵消了，实际上是最大的 + 第二大的数字，这是一个红鲱鱼）。

在第二行中，最大的总和是通过取整个序列来实现的：

2 + 3 + -2 + -1 + 10

总和为 12。

于 2012-09-04T10:23:46.100 回答
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 回答
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 回答