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(1..i).

Algorithm

Trace Output

basic.f90

program array_sum
    implicit none
    integer :: arr(8) = [3, 1, 4, 1, 5, 9, 2, 6]
    integer :: total, i
    total = 0
    do i = 1, 8
        total = total + arr(i)
    end do
    print '(I0)', total
end program array_sum

trace.f90

program array_sum_trace
    implicit none
    integer :: arr(8) = [3, 1, 4, 1, 5, 9, 2, 6]
    integer :: total, i, before
    total = 0
    do i = 1, 8
        before = total
        total = total + arr(i)
        print '(A,I0,A,I0,A,I0,A,I0,A,I0)', 'step ', i, &
            ': arr(', i, ')=', arr(i), ' total ', before, ' -> ', total
    end do
    print '(A,I0)', 'final total = ', total
end program array_sum_trace

Complexity

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

Implementation notes

Fortran: use an explicit do i = 1, 8 loop. Calling sum(arr) 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. The trace variant prints step i: arr(i)=V total B -> T for each visit and a closing final total = 31 summary.

linear scan Visit each element exactly once in index order.

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