Print Longest Decreasing Segment I'm trying to brush up on my Dynamic Programming by doing some example problems. I've got the following...

Given an array of integers, print the longest decreasing segment.

For example {4,3,2,1,5,6,7,6,5,4,3,2,1} would print "7, 6, 5, 4, 3, 2, 1"

The following is my solution.. I think it looks okay and it has a decent O(n) runtime. However, the space complexity is O(n^2) due to the extra "length" array storing state. Is it possible to get rid of it? Any other problems? 

int[] segment = {4,3,2,1,5,6,7,6,5,4,3,2,1};
int[] length =  {0,0,0,0,0,0,0,0,0,0,0,0,0};

public String getDecreasingSegment(){

    int maxStart = 0;
    int maxEnd = 0;

    for(int i = 1; i &lt; segment.length; i++){

        if(segment[i] &lt; segment[i-1]){

            length[i] = length[i-1]+1;

            if(length[i] &gt; length[maxEnd]){

                maxEnd = i;
                maxStart = maxEnd - length[maxEnd];

            }

        }else{

            length[i] = 0;

        }

    }

    StringBuffer buff = new StringBuffer();

    for(int i = maxStart; i &lt;= maxEnd; i++){

        buff.append(segment[i] + ", ");

    }

    return buff.toString();
}
As said above adding an extra Array does not change the space complexity to n^2. 


Another thing is you do not need that extra Array also. All you need is 3 or 4 variables. 
You can store the previous beginIndex and length of and the currentBeginIndex and length and if it crosses the previous maxLength then store the max as the crrentMax else continue with the iteration. 


Let me know if you want some code sample.