find largest sum of 3 consecutive integers from inputs (Java)-CodePudding

I am having troubles writing a program that takes unknown amount of integers as inputs and finding the largest sum of 3 consecutive ints

if user inputs 999 then we need to close input

can't use arrays

for example

Please enter numbers followed by 999:

7 2 **9 8 7** 6 7 5 9 999

The max sum is 24

because 9 8 7 = 24 (9,8,7 makes the greatest sum of consecutive numbers)

the goal: take input as long is inputs != 999, print greatest sum of 3 consecutive numbers (999 excluded). if less than 3 inputs entered, print all inputs' sum.

my English isn't that good so I hope I made it clear enough

any ideas will be great, I don't even know how to begin. thanks.

public static void main(String[] args) {
        
        System.out.print("Please enter numbers followed by 999: ");
        int num=0, sum=0, maxSum=0;
        
        while (num != 999) {
            num = input.nextInt();
        }
        
        
        System.out.println("The max sum is ");
        
        input.close();
    }

}

CodePudding user response：

Sliding Window Algorithm Technique is your friend! You can do it with O(n).

public static long findThreeConsecutiveSum(Iterator<Integer> it) {
    long maxSum = Long.MIN_VALUE;
    long curSum = 0;
    Deque<Integer> deque = new ArrayDeque<>(4);

    while (it.hasNext()) {
        int val = it.next();

        curSum  = val;
        deque.addLast(val);

        if (deque.size() == 4) {
            curSum -= deque.removeFirst();
        }

        maxSum = Math.max(maxSum, curSum);
    }


    return maxSum;
}

Demo

List<Integer> values = List.of(7, 2, 9, 8, 7, 6, 7, 5, 9);
long maxSum = findThreeConsecutiveSum(values.iterator());
System.out.println(maxSum); // 24

CodePudding user response：

Since this is homework, I'm not going to write the code.

Let's take your example. I'm assuming that all input values will be positive integers.

7 2 9 8 7 6 7 5 9 999

Now, how would you do this with a pencil and paper?

You have to save 3 numbers. An array would be helpful here, but since you can't use an array, you can define 3 int values to hold the previous values. We also define a sum and maxSum.

value1 = 0
value2 = 0
value3 = 0
sum = 0
maxSum = 0

So, the first number is 7. After reading 7, we now have the following on paper.

value1 = 7
value2 = 0
value3 = 0
sum = 7
maxSum = 7

The next number is 2. After reading 2, we now have the following on paper.

value1 = 7
value2 = 2
value3 = 0
sum = 9
maxSum = 9

The next number is 9. After reading 9, we now have the following on paper.

value1 = 7
value2 = 2
value3 = 9
sum = 18
maxSum = 18

The next number is 8. After reading 8, we now have the following on paper.

value1 = 2
value2 = 9
value3 = 8
sum = 19
maxSum = 19

Notice how the numbers stored in value1 through value3 have shifted. You keep the last three values.

You can work out how reading the rest of the values works using the same method.

You walk through the algorithm using a pencil and paper.