title: Why is the maximum sum subarray brute force O(n^2)?
body: <p>The <a href="https://en.wikipedia.org/wiki/Maximum_subarray_problem" rel="nofollow noreferrer">maximum subarray sum</a> is a famous problem in computer science.</p>
  <p>There are at least two solutions:</p>
  <ol>
  <li>Brute force, find all the possible sub arrays and find the maximum.</li>
  <li>Use a variation of <a href="https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm" rel="nofollow noreferrer">Kadane's Algorithm</a> to compute the global max while going through the first pass of the array.</li>
  </ol>
  <p>In a video <a href="https://www.youtube.com/watch?v=86CQq3pKSUw" rel="nofollow noreferrer">tutorial</a> the author mentions the brute force method is <code>O(n^2)</code>, reading <a href="https://stackoverflow.com/a/5649948/2909897">another answer</a> one person thinks it <code>O(n^2)</code> and another thinks it's <code>O(n^3)</code>.</p>
  <p>Is the brute force <code>O(n^2)</code> or <code>O(n^3)</code>? And more importantly can you illustrate what analysis you performed on the brute force method to know it's <code>O(?)</code>?</p>