# 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 < segment.length; i++){

if(segment[i] < segment[i-1]){

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

if(length[i] > length[maxEnd]){

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

}

}else{

length[i] = 0;

}

}

StringBuffer buff = new StringBuffer();

for(int i = maxStart; i <= maxEnd; i++){

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

}

return buff.toString();
}

• Having an extra array doesn't imply a space complexity of O(n^2). Your space complexity is still O(n). – Olayinka Sep 11 '13 at 4:16
• Just to clarify for OP: With space complexity of O(n^2), if you had 5 elements, your algoritm would use 5*5 = 25 memory used for integers. Since you are only creating two arrays, your memory used would be 5*2 = 10. This makes it linear, not quadratic. – aglassman Sep 11 '13 at 16:27