我刚开始写，如果有错误的话，请指出来。 如果说明不明确的话，也请大家指出。
领先优势
求解数组中最大升序/降序子序列长度的问题通过使用C语言动态规划来实现。
原题
长入子查询
Given an unsorted array of integers，findthelengthoflongestincreasingsubsequence。
For example，
given [ 10，9，2，5，3，7，101，18 ]，
thelongestincreasingsubsequenceis [ 2，3，7，101 ]，thereforethelengthis4. notethattheremaybemorethanoneliscombination，tion
youralgorithmshouldrunino(N2 ) complexity。
follow up : couldyouimproveitto (nlogn ) time complexity？
Credits:
specialthanksto @ pbrotherforaddingthisproblemandcreatingalltestcases。
subscribetoseewhichcompaniesaskedthisquestion。
翻译：
给出无序整形数组，找到其最大的升序子序列。
举个例子，
样品序列arr [ ]={ 10，9，2，5，3，7，101，18 }，
数组arr的最长升序子列为{ 2，3，7，101 }，因此长度为4。
请注意，可能有多个最长上升子序列(LIS )的组合。 只需要返回的长度就可以了。
以时间复杂度o(n )为前提来实现。
高度：在时间复杂性o(nlogn )的前提下实现。
以下不翻译。
正文
以下是注释掉log相关代码，贴上分步log，简要概述思路，共同学习进步的两种时间复杂度的c语言解法。
o(n ) )。
想法：
定义一个数组lis，它记录以目标序列nums[0]开始并以每个元素结束的子列的最大升序子列长度。
取出lis的最大值是结果。
重要判断是代码中的if(nums[I]nums[j]lis[j]1lis[I] )。
//这是O(N2 )的方法
intlengthoflis_01(int*nums，int numsSize )。
if (编号大小2 ) {
return numsSize；
}
int lis[numsSize]；
//打印(original array : )；
//printarray(Nums，numsSize )；
//这个for循环只是为了log的美观而没有意义
//for(intI=0； i numsSize； I ) {
//lis[i]=0；
//}
int i，j，result=0；
for(I=0； i numsSize； I ) {
lis[i]=1；
for(j=0； j i； j ) {
if(nums[I]nums[j]lis[j]1lis[I] ) {
lis[i]=lis[j] 1；
}
}
result=result lis[i]？ result : lis[i]；
//printarray(lis，numsSize )；
}
返回结果；
}
o(n ) lengthOfLIS_01的Log ) )为了便于观察和理解在打印时隐藏了值为0的元素) )。
这里打印的是记录以各要素结束的子列中升序最大的子列的长度的数组。
original array 336010、9、2、5、3、7、80、18、1、2、3、4、5、6、7、8、9，
1、
一，一，
一，一，一，
一，一，一，二，
一，一，一，二，二，
一，一，一，二，二，三，
一，一，一，二，
2, 3, 4,1, 1, 1, 2, 2, 3, 4, 4,
1, 1, 1, 2, 2, 3, 4, 4, 1,
1, 1, 1, 2, 2, 3, 4, 4, 1, 2,
1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3,
1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3, 4,
1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3, 4, 5,
1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3, 4, 5, 6,
1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3, 4, 5, 6, 7,
1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3, 4, 5, 6, 7, 8,
1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3, 4, 5, 6, 7, 8, 9,
result = 9
O(nlogn)
思路：
定义数组tmp记录当前最大升序子串(∴tmp必然升序)，用tmp的末位元素对比目标序列nums[1]开始的每个元素，若当前nums元素 > tmp末位元素，当前nums元素插入tmp。否则用当前nums元素替换tmp中合理位置元素即可。
// 折半(二分)查找
int binarySearch(int *array, int lenght, int key) {
int low = 0;
int high = lenght - 1;
int middle;
while (low <= high) {
middle = low + (high - low) / 2;
if (array[middle] > key) {
high = middle - 1;
} else if (array[middle] < key) {
low = middle + 1;
} else {
return middle;
}
}
return low;
}
// 此为O(nlog(n))方法
int lengthOfLIS_02(int* nums, int numsSize) {
// 长度若为0或1，无须比较直接返回
if (numsSize < 2) {
return numsSize;
}
// 声明临时数组，赋值首元素，当前lenght = 1
int tmp[numsSize], position;
// printf("OriginalArray:");
// printArray(nums, numsSize);
// // 此for循环只是为了log美观 无意义
// for (int i =0; i < numsSize; i++) {
// tmp[i] = 0;
// }
tmp[0] = nums[0];
int lenght = 1;
// 遍历nums[1]~nums[numsSize-1]
for (int i = 1; i < numsSize; i++) {
// 若当前nums元素 > tmp最大元素，插入tmp，length++
if (nums[i] > tmp[lenght - 1]) {
tmp[lenght] = nums[i];
lenght++;
// printf("Part-A i=%2d len=%2d Arr:", i, lenght);
} else {
// 二分定位 用当前nums元素 替换 tmp中合理位置元素
position = binarySearch(tmp, lenght, nums[i]);
tmp[position] = nums[i];
// printf("Part-B i=%2d pos=%2d Arr:", i, position);
}
// printArray(tmp, numsSize);
}
// printf("Finishedn");
// printArray(tmp, numsSize);
return lenght;
}
O(nlogn) lengthOfLIS_02 的 Log(为了便于观察理解 打印时隐去了值为0的元素)
OriginalArray:10, 9, 2, 5, 3, 7, 80, 18, 1, 2, 3, 4, 5, 6, 7, 8, 9,
Part-B i= 1 pos= 0 Arr: 9,
Part-B i= 2 pos= 0 Arr: 2,
Part-A i= 3 len= 2 Arr: 2, 5,
Part-B i= 4 pos= 1 Arr: 2, 3,
Part-A i= 5 len= 3 Arr: 2, 3, 7,
Part-A i= 6 len= 4 Arr: 2, 3, 7, 80,
Part-B i= 7 pos= 3 Arr: 2, 3, 7, 18,
Part-B i= 8 pos= 0 Arr: 1, 3, 7, 18,
Part-B i= 9 pos= 1 Arr: 1, 2, 7, 18,
Part-B i=10 pos= 2 Arr: 1, 2, 3, 18,
Part-B i=11 pos= 3 Arr: 1, 2, 3, 4,
Part-A i=12 len= 5 Arr: 1, 2, 3, 4, 5,
Part-A i=13 len= 6 Arr: 1, 2, 3, 4, 5, 6,
Part-A i=14 len= 7 Arr: 1, 2, 3, 4, 5, 6, 7,
Part-A i=15 len= 8 Arr: 1, 2, 3, 4, 5, 6, 7, 8,
Part-A i=16 len= 9 Arr: 1, 2, 3, 4, 5, 6, 7, 8, 9,
Finished
1, 2, 3, 4, 5, 6, 7, 8, 9,
result = 9
相关的其他函数(非重要内容 可忽略)
void testCode() {
int arr[] = {10,9,2,5,3,7,80,18,1,2,3,4,5,6,7,8,9};
// int arr[] = {3,5,6,2,5,4,19,5,6,7,12};
// int count = lengthOfLIS_01(arr, sizeof(arr)/sizeof(int));
int count = lengthOfLIS_02(arr, sizeof(arr)/sizeof(int));
printf("result = %dn", count);
}
void printArray(int *a, int count) {
for (int i = 0; i < count; i++) {
if (a[i] != 0)
printf("%2d ,",a[i]);
}
printf("n");
}