Sum and Maximum of Input Numbers

easy Programming Basics

Problem

The first line has a number n (n is at least 1). The second line has n integers. Print their sum on the first line (Sum: <sum>) and the largest number on the second line (Maximum: <max>).

Constraints

  • 1 <= n <= 10^5
  • -2^31 <= each number < 2^31

Examples

Input

5
3 1 4 1 5

Output

Sum: 14
Maximum: 5

Solutions

Best approachTime O(n)Space O(1)

We read the numbers one by one. For each number we update two values: the sum and the maximum. We start the maximum with the first number, because a start value like 0 would be wrong for negative numbers.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Read n numbers and print their sum and maximum.
 * Input   : First line n, second line n integers.
 * Output  : Two lines: Sum and Maximum.
 * Approach: Read in a loop and keep two variables.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Step 1: Read how many numbers will follow.
        int count = scanner.nextInt();

        // Step 2: Use long for the sum, because many large int values can overflow an int.
        long sum = 0;

        // Step 3: Read the first number. It is the maximum for now.
        int maximum = scanner.nextInt();
        sum = sum + maximum;

        // Step 4: Read the other numbers in a loop.
        for (int index = 1; index < count; index++) {
            int number = scanner.nextInt();

            // Step 5: Add the number to the sum and update the maximum if the number is larger.
            sum = sum + number;
            if (number > maximum) {
                maximum = number;
            }
        }

        // Step 6: Print the results.
        System.out.println("Sum: " + sum);
        System.out.println("Maximum: " + maximum);
    }
}
Hints (1)
  1. Why is 0 a bad start value for the maximum?