d[i] i為結(jié)尾的最長遞增子序列，
d[0] = 1 ,
d[i] 算出 [0,i) 找出d[i] > d[[0,i)] ,同時d[[0,i)] 中的最大值加一
然后算出最大的d[]
int lengthOfLIS(int* nums, int numsSize) {
int *lis, i, j, max = 0;
lis = (int*) malloc ( sizeof( int ) * numsSize );
/* Initialize LIS values for all indexes */
for (i = 0; i < numsSize; i++ )
lis[i] = 1;
/* Compute optimized LIS values in bottom up manner */
for (i = 1; i < numsSize; i++ )
for (j = 0; j < i; j++ )
if ( nums[i] > nums[j] && lis[j] + 1 > lis[i])
lis[i] = lis[j] + 1;
/* Pick maximum of all LIS values */
for (i = 0; i < numsSize; i++ )
if (max < lis[i])
max = lis[i];
/* Free memory to avoid memory leak */
free(lis);
return max;
}
