Maximum increasing subsequence with dynamic programming

Question

The problem is as follows: Given a sequence L of n integers not necessarily distinct , write an algorithm that computes the increasing subsequence of maximum length :

The recurrence equation that I developed is this:

I start the index from 0:

If j = n opt(j) = 0 (base case)
otherwise opt(j) = max j <i <= n such that Lj <Li = {opt(i) +1}

do you think is right to do so? the standard solution used for this typical problem is to first calculate the maximum increasing subsequence ending in Li for all elements of the sequence and then the maximum on these values, that is:

if i = 1 opt (i) = 1
otherwise opt (i) = max 1 <= j <= i-1 and Lj <Li = {opt (i)} +1

and then the max on these elements.

so I wanted to know if you think my solution was right anyway.

Why you want a dynamic-programming solution which run in O(N^2) where there already exists a binary search solution which can be finished in O(N logN)? see https://stackoverflow.com/questions/6129682/longest-increasing-subsequenceonlogn — DU Jiaen, Dec 28 '17 at 09:09

score 1 · Accepted Answer · answered Feb 03 '11 at 18:31

Here's a hint: The loop invariant that will be trying to preserve in the algorithm is that a variable, k = index of the beginning of the longest increasing subsequence. So as you iterate through the sequence of integers [0...n] you increment the k value accordingly.

score 0 · Answer 2 · answered Apr 23 '13 at 18:05

// Given an array of Integers, find the length of Longest Increasing Subsequence and print the sequence.

int longsub (int a[], int len) {

    int localsum = 0;
    int i = 0;
    int begin = i;
    int localsublen = 1;
    int globalsunlen = 0;
    int end = i;

    for (i=1; i< len; i++)    {

        if (a[i] > a[i-1]) {
              localsublen++;
        }
        else {
            newbegin = i;
            localsublen = 1;
        }

        if (localsublen > globalsublen)    {
            begin = newbegin;
            end = i;
            globalsublen = localsublen;
        }
    }

    for (i=begin;i <= end; i++)    
        printf ("%d.\n",a[i]);


}

I don't think this is correct. for example, consider [1,5,6,2,7], your code will results in [1,5,6] but in fact the optimal is [1,5,6,7]. — DU Jiaen, Dec 28 '17 at 09:12

Maximum increasing subsequence with dynamic programming

2 Answers2