Time complexity about Maximum subarray

Question

I recently came across a function called the strawman algorithm which the pseudo code looks like this:

StrawmanSubarray(A):
 Initialize bestsum = A[0] 
 For left=0 to n-1:
 For right = left to n-1:
 Compute sum A[left] + . . . + A[right]
 If sum > bestsum: bestsum = sum

The time complexity is Θ (n^3), and I don't quite get where is the 3rd n comes from to get Θ (n^3)?

• BearAqua the Logician: How many operations can computing $A[left]+...+A[right]$ be?
• BearAqua the Logician: You're wrong; it matters. It is exactly what causes your confusion.
• plop: You have right-left-1 sums in the line that starts with Compute . This line is repeated by the inner for for right = left to n-1 and the outer for repeats its content for left=0 to n-1. So, the number of sums is $\sum_{l=0}^{n-1}\sum_{r=l}^{n-1}(r-l-1)=\frac{n (n^2 - 3 n - 4)}{6}$. However, the line Compute could be implemented in such a way that each iteration does only one sum. In this case the number of sums is $\sum_{l=0}^{n - 1}( \sum_{r=l}^{n - 1} 1) = \frac{n (n + 1)}{2}$.
• sctts-lol: @BearAqua ok sure, let's assume the array length is n=8?
• sctts-lol: @plop sorry I am still a newbie, how do you get the formula n(n^2-3n-4)/6? thanks