Array Sum (Linear Scan)

Walk an array once, accumulating each element into a running total. This is the canonical single-pass linear scan and the simplest possible loop invariant: after step i, total equals the sum of arr[0..i].

Algorithm

Trace Output

Basic.java

public class Basic {
    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
        int total = 0;
        for (int i = 0; i < arr.length; i++) {
            total = total + arr[i];
        }
        System.out.println(total);
    }
}

Trace.java

public class Trace {
    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
        int total = 0;
        for (int i = 0; i < arr.length; i++) {
            int before = total;
            total = total + arr[i];
            System.out.println("step " + i + ": arr[" + i + "]=" + arr[i]
                + " total " + before + " -> " + total);
        }
        System.out.println("final total = " + total);
    }
}

Complexity

Time: O(n)
Space: O(1)

Implementation notes

Java: use the explicit for (int i = 0; i < arr.length; i++) loop and int total. Calling Arrays.stream(arr).sum() would hide the iteration the lesson is teaching.
The replay shows i, arr[i], and total before and after each addition, matching the lesson spec's state-transition table.

linear scan Visit each element exactly once in index order.

running total `total` accumulates the sum as the loop advances.