2.16 求数组中最长递增子序列
问题：
如标题，求数组中最长递增子序列。
解法一：
动态规划
#include <stdio.h>#include <stdlib.h>#include<malloc.h>int Min(int* array, int num){ int i = 0; int min = array[0]; for (i = 1; i < num; i++) { if (array[i] < min) min = array[i]; } return min;}int LIS(int* array, int num){ int i = 0, j = 0; int* temp = (int *)malloc((num + 1) * sizeof(int)); int* LIS = (int *)malloc(num * sizeof(int)); temp[1] = array[0]; temp[0] = Min(array, num) - 1; for (i = 0; i < num; i++) { LIS[i] = 1; } int nMaxLIS = 1; for(i = 1; i < num; i++) { for(j = nMaxLIS; j >= 0; j--) { if (array[i] > temp[j]) { LIS[i] = j + 1; break; } } if (LIS[i] > nMaxLIS) { nMaxLIS = LIS[i]; temp[LIS[i]] = array[i]; } else if (temp[j] < array[i] && array[i] < temp[j + 1]) { temp[j + 1] = array[i]; } } return nMaxLIS;}int main(){ //printf("Hello world!\n"); int array[] = {1,-1,2,-3,4,-5,6,-7}; printf("%d\n", LIS(array, 8)); return 0;}