1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

// 08_LIS.cpp : Defines the entry point for the console application.
//
/*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/8/4
*/

/*
Problem: Given a sequence s1,s2,…,sN of integers, find a longest increasing subsequence

Algorithm: We compute F*(j) for j=1,2,…,N
where F*(j) is the length of the longest increasing subsequence
of s1,s2,…,sJ that includes sJ

Step 1: Def of subproblem
Step 2: Solution obtained by taking Max{F*(1), F*(2), …, F*(N)}
Step 3: Base case: F*(1)=1
Step 4: Order of subproblems: F*(1), then F*(2), then F*(3)., etc., up to F*(N)
Step 5: For j>1,                        F*(j) = maxk {1,F*(k)+1 : k<j, and sk < sj}
*/

#include "stdafx.h"

void Print(int *array, int n)
{
    ; i < n; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int Max(int *array, int n)
{
    ];
    ; i < n; i++)
    {
        if (result < array[i])
        {
            result = array[i];
        }
    }
    return result;
}

int LIS(int *array, int n)
{
    // O(n^2)---->O(n*lgn)
    int *f = new int[n];
    // base cases
;
    ; j < n; j++)
    {
        f[j] = ;
        ; k < j; k++)
        {
             > f[j])
            {
                f[j] = f[k] + ;
            }
        }
    }
    // print result
    Print(array, n);
    Print(f, n);

int result = Max(f, n);
    delete []f;
    return result;
}

void test_case(int *a, int n)
{
    int result = LIS(a, n);
    printf("max length of LIS is %d", result);
}

void test_default()
{
    };
    test_case(a, );
}

void test_main()
{
    test_default();
}

int _tmain(int argc, _TCHAR *argv[])
{
    test_main();
    ;
}
/*
8 5 1 38 4 2 9 75 6 16 3 8 10
1 1 1 2 2 2 3 4 3 4 3 4 5
max length of LIS is 5
*/