Нахождение наибольшей суммы последовательных чисел в массиве

Question

У меня есть несколько вопросов к этой программе, которые я задаю, чтобы найти наибольшую сумму последовательных чисел в списке. Имейте в виду, это не то же самое, что найти наибольшую сумму смежных целых чисел в массиве. В основном, дан список для бывших. 2, -1, 3,4,9 .... и т.д. до 1 миллиона, мне нужно найти наибольшую сумму последовательных чисел (в приведенном выше списке 3,4 являются последовательными, поэтому сумма будет равна 7). Так что я могу понять, что мне нужен цикл, который просматривает список и проверяет, являются ли числа последовательными. Я основал свой цикл на том факте, что последовательные числа при вычитании будут равны -1, но мой оператор if всегда, кажется, получает ошибку ArrayINdexOutOfBounds. Для примера скажем, что список

1 2 3 4
3 -1 4 5

Вот мой код;

public class ProgramCRedo {

//This method reads each line and checks for the largest sum of consecutive numbers in a list
//This method does not have a return value, information is outputted once it exists
//This method has one parameter, it is string list taken from the input file
public static void checkLine (String line){
    String[] numbers = line.split(" ");
    int sum = 0;
    int largestSum = 0; 
    int [] savedNums = new int [numbers.length];

    for(int i = 0; i<savedNums.length; i++) { //loops through the list
        savedNums [i] = Integer.parseInt(numbers[i]);
        if((savedNums[i] - (savedNums[i+1])) == -1) { //checks if numbers are consecutive
            sum += (savedNums[i] + (savedNums[i+1])); //if true, adds them up to a sum
        }
        System.out.println(sum);
//          System.out.println(savedNums[i]);
        }
    }
}
public static void main(String[] args) {

    try{
        BufferedReader bf = new BufferedReader (new FileReader("input.txt"));
        String line;

        line = bf.readLine(); //reads line
        //String line1= null; //skips first line    

        while(line != null){    //keeps looping until no more lines     
            checkLine(line); // uses list to check each line in file
            line = bf.readLine();
        }
        bf.close();

    }catch(FileNotFoundException e){ // catches exceptions
        System.out.println("FILE NOT FOUND!");
    }catch(IOException e){
        System.out.println("Reading Error!");
    }catch(NumberFormatException e) {
        System.out.println("Invalid Input Entered");
    }

    System.out.println("Program is complete");
}

Вот некоторые из вопросов, которые у меня есть

1. Почему мой оператор if в методе дает мне исключение ArrayIndexOutOfBounds?
2. В задании указано, что список целых чисел для каждого тестового примера будет дан в одной строке текста с одним пробелом, разделяющим каждое целое число в списке. Можно предположить, что максимальный размер списка для каждого случая будет 1 000 000 - где и как мне ввести эту проверку для максимального списка 1 миллион целых чисел?

Спасибо, это в JAVA, кстати.

ОБНОВЛЕНИЕ: Я выяснил проблему с массивом за пределами границ. Теперь происходит то, что когда я распечатываю сумму для приведенного здесь примера списка, я получаю 0 и -1. Что не правильно. Я попытаюсь это выяснить, но если у кого-то есть идеи, пожалуйста, дайте мне знать.

Answer 1

В задании указано, что список целых чисел для каждого тестового примера будет представлен в одной строке текста с одним пробелом, разделяющим каждое целое число в списке.Вы можете предположить, что максимальный размер списка для каждого случая будет 1 000 000 - где и как мне ввести эту проверку для максимального списка 1 миллион целых чисел?

Приведенное выше утверждение говорит вам, чтобудет 1 миллион целых чисел, если вам нужно инициализировать массив целых чисел.Но поскольку в вашем случае вы используете String[] numbers = line.split(" ");, вам не нужно об этом беспокоиться.Но если ваш профессор действительно хотел исключить те строки, которые содержат более 1 миллиона целых чисел, то один из способов - это поставить проверку после String[] numbers = line.split(" "); (проверьте код ниже для подробностей)

Теперь что происходитчто, когда я распечатываю сумму для приведенного здесь примера списка, я получаю 0 и -1.Что не правильно.Я попытаюсь это выяснить, но если у кого-то есть идеи, пожалуйста, дайте мне знать.

Вышеприведенное утверждение происходит, поскольку ваш код никогда не будет верным для этой строки:

if((savedNums[i] - (savedNums[i+1])) == -1) {

Условие никогда не будет оцениваться в true, потому что вы просто инициализируете свой savedNums, выполняя int [] savedNums = new int [numbers.length];, что означает, что если numbers.length равно 3, то savedNums будет [0, 0, 0], поскольку значения по умолчанию для массива int равны 0.

Вы устанавливаете значение каждого элемента savedNums, пока вы итерируете цикл, выполнив savedNums [i] = Integer.parseInt(numbers[i]);, таким образом, savedNums[i+1] всегда приведет кв 0.

Также неверно выполнение sum += (savedNums[i] + (savedNums[i+1]));, потому что некоторые элементы будут добавлены дважды в sum.
Например, если у вас есть savedNums = [1, 2, 3], тогда значение суммы в каждом из них будет:
Первая итерация:

i = 0;
sum = 0; // initial
sum = sum + savedNums[i] + savedNums[i+1];
sum = 0 + 1 + 2;
sum = 3;

Вторая итерация:

i = 1;
sum = 3; // value after first iteration
sum = sum + savedNums[i] + savedNums[i+1];
sum = 3 + 2 + 3; // 2 was added twice
sum = 8;

Таким образом, ваш sum будет 8 вместо 6.

Я изменил ваш кодчтобы все работало так, как ожидалось, просто прочитайте комментарии к коду для получения подробной информации.

public static void checkLine(String line) {
    String[] numbers = line.split(" ");
        if (number.length > 1000000) { //if line contains more than 1 million integers
                 return;
        }
    int sum = 0;
    int largestSum = 0;

    for (int i = 0; i < numbers.length - 1; i++) { // loops through the list
        int currentNum = Integer.parseInt(numbers[i]);
        int nextNum = Integer.parseInt(numbers[i + 1]);
        if (nextNum - currentNum == 1) { // checks if numbers are consecutive
            // check if sum is 0, which means that this is the first time a consecutive
            // number is found
            // example [1,2,3,4]
            if (sum == 0) { // this will be true when currenNum is 1 and nextNum is 2
                sum = currentNum + nextNum; // since it is the first time a consecutive number is found add both
                                            // numbers
            } else { // this will be executed when currenNum is 2 and nextNum is 3
                sum += nextNum; // since it is not the first time a consecutive number is found only add the
                                // next number, no need to add the current number since it is already added in
                                // the above condition
            }
        } else {
            sum = 0;
        }
        if (largestSum < sum) {
            largestSum = sum;
        }
    }

    System.out.println(sum);
}

Пример ввода:

1 2 3 4
3 -1 4 5
1 2 4 5

Выход:

10
9
9