Maximum contiguous subsequence -- dynamic programming or greedy algorithm?
<p>Given an array <code>vector&lt;int&gt; arr</code> with positive and negative entries, the maximum contiguous subsequence problem requires to find a (contiguous) segment of the array <code>arr</code> with maximum sum. Sum of empty segment is zero. The C++ code of the algorithm I'm using is as follows:</p>

<pre><code>  int MaxContSum(const vector&lt;int&gt;&amp; arr){
    int i,sum=0,max=0;
    for(i=0;i&lt;arr.size();i++){
      if(arr[i]&gt;=0) {if(sum&lt;0) sum=0;}
      else {if(sum&gt;max) max=sum;}
      sum+=arr[i];
    }
    if(sum&gt;max) max=sum; return max;
  }
</code></pre>

<p>Is this algorithm a greedy algorithm or dynamic programming? It looks like it's just scanning the entries one by one and applying different strategies based on whether <code>arr[i]</code> is potive or negative, a locally checkable condition. Why does this problem appear in the dynamic programming chapter, then?</p>