title: Algorithmic complexity of naive code for processing all consecutive subsequences of a list: n^2 or n^3?
body: <p>I'm studying for a test and found this question: </p>
  
  <p>I can't really determine the complexity, I figured it's either O(n<sup>2</sup>) or O(n<sup>3</sup>) and I'm leaning towards O(n<sup>3</sup>).<br>
  Can someone tell me what it is and why?</p>
  
  <p>My idea that it's O(n<sup>2</sup>) is because in the <code>j</code> loop, <code>j = i</code> which gives a triangle shape, and then the <code>k</code> loop goes from <code>i + 1</code> to <code>j</code>, which I think is the other half of the triangle.</p>
  
  <pre><code>public static int what(int[] arr)
  {
      int m = arr[0];
      for (int i=0; i&lt;arr.length; i++)
      {
          for (int j=i; j&lt;arr.length;j++)
          {
              int s = arr[i];
              for (int k=i+1; k&lt;=j; k++)
               s += arr[k];
              if (s &gt; m)
               m = s;
          }
      }
      return m;
  }
  </code></pre>
  
  <p>Also if you can tell me what it does? </p>
  
  <p>I figured it returns the addition of positive integers or the biggest integer in the array.<br>
  But for arrays like <code>{99, -3, 0, 1}</code> it returns <code>99</code>, which I think is because it's buggy. If not than I have no Idea what it does:</p>
  
  <pre><code>{99, 1} =&gt; returns 100
  {-1, -2, -3} =&gt; return -1
  {-1, 5, -2} =&gt; returns 5
  {99, -3, 0, 1} =&gt; returns 99 ???
  </code></pre>