(n (n+1) ) / 2, but how?

All subsets vs all contiguous subsets

All subsets is n², and we know that contiguous and non contiguous are subsets. So the upper bound is n².

Geometric Visualization

Let's begin by manually calculating all the subarrays by hand on a small example. The formula claims we should have 10 unique subarrays for an array size of n = 4. We can verify that by drawing them all out.

Without the numbers, this can also be drawn as the following

Now let's circle back and draw the full n² grid.

The area of an nxn grid is n². The diagonal of an nxn grid will always be n. So let's get rid of the diagonal to get n² - n.

This leaves two perfect triangle. One with our data and one without our data. This means that the triangle with the data we want is (n² - n) / 2

Lastly, let's add be the diagonal (which was size n) back to the triangle we just calculated. This gets us (n (n+1) ) / 2.

Gauss' sum trick

You can also derive the same solution by using Gauss's trick where you add the opposite of a series to itself then solve for it.

Induction Proof

And lastly a quick induction proof to make sure the formula works

Sources

Some videos along the way that I referenced and wanted to credit:

Induction proof:

Gauss' arithmetic sums trick: