1
\$\begingroup\$

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();
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Having an extra array doesn't imply a space complexity of O(n^2). Your space complexity is still O(n). \$\endgroup\$ – Olayinka Sep 11 '13 at 4:16
  • \$\begingroup\$ 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. \$\endgroup\$ – aglassman Sep 11 '13 at 16:27
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.