[zucker42]

Brute is choosing every index pair (n^2) and calculating the sun of their subarray (n). With prefix sums you can get to n^2.