编程算法|编程算法 - 最长上升子序列问题 代码(C)
最长上升子序列问题 代码(C)
本文地址: http://blog.csdn.net/caroline_wendy
题目: 有一个长为n的数列a. 请求出这个序列中最长上升子序列的长度. 最长上升子序列的数字之间能够有间隔.
即最长上升子序列(LIS, Longest Increasing Subsequence), 比如: n=5, a={4,2,3,1,5}, result=3(2,3,5).
【编程算法|编程算法 - 最长上升子序列问题 代码(C)】使用动态规划求解(DP).
方法1: 依次求出每一个数字之前的最长上升子序列, 时间复杂度O(n^2).
方法2: 求取针对最末位的元素的最长子序列, 使用较小的元素更新数组, 应用二分搜索查找元素, 时间复杂度(nlogn).
代码:
/*
* main.cpp
*
*Created on: 2014.7.20
*Author: Spike
*//*eclipse cdt, gcc 4.8.1*/#include /*
* main.cpp
*
*Created on: 2014.7.20
*Author: spike
*//*eclipse cdt, gcc 4.8.1*/#include
#include
#include #include using namespace std;
class Program {
static const int MAX_N = 100;
const int INF = INT_MAX>>2;
int n = 5;
int a[MAX_N] = {4, 2, 3, 1, 5};
int dp[MAX_N];
public:
void solve() {
int res = 0;
for (int i=0;
i
输出:
result = 3
文章图片
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- python青少年编程比赛_第十一届蓝桥杯大赛青少年创意编程组比赛细则
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- HTML基础--基本概念--跟着李南江学编程
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 我的软件测试开发工程师书单