最长不下降子序列（动态规划：LIS）

本文主要是介绍最长不下降子序列（动态规划：LIS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

d[i] = 以第i个数字为最大值的最长不下降子序列个数字个数。

当 j < i , a[i] >= a[j]，d[i] = max{ d[j] + 1 } ；

否则 d[i] = 1。

int LIS(int a[], int n)
{int d[1000];memset(d, 0, sizeof(d));for(int i = 0; i < n; i++){d[i] = 1;for(int j = 0; j < i; j++){if(a[i] >= a[j] && d[j]+1 > d[i]){d[i] = d[j] + 1;}}}printf("%d\n", d[n-1]);return d[n-1];
}

这篇关于最长不下降子序列（动态规划：LIS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---