**Problem:** Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

Reference: http://codercareer.blogspot.com/2011/10/no-16-maximum-length-of-incremental.html

/* Copyleft: Ming Lin <minggr@gmail.com> */ #include <stdio.h> #include <stdlib.h> int maximal(int data[], int n) { int *max; int i, j; int m, r; int cur; max = malloc(sizeof(int)*n); r = -1; max[0] = 1; for (i = 1; i < n; i++) { m = -1; for (j = 0; j < i; j++) { if (data[i] > data[j]) { cur = max[j] + 1; } else cur = 1; if (m == -1 || cur > m) m = cur; } max[i] = m; if (r == -1 || max[i] > r) r = max[i]; } free(max); return r; } int main() { int data[] = {7,2,3,1,5,8,9,6}; int n = 8; printf("%d\n", maximal(data, n)); return 0; }