//****************************************************************************************************
//
// 求一个数组的最长递减子序列 - C++ - by Chimomo
//
// 题目: 求一个数组的最长递减子序列,比如{8, 14, 6, 2, 8, 14, 3, 2, 7, 4, 7, 2, 8, 101, 23, 6, 1, 2, 1, 1}的最长递减子序列为{14,8,3,2,1}。
//
// Answer: Scan from left to right, maintain a decreasing sequence. For each number, binary search in the decreasing sequence to see whether it can be substituted.
//
//****************************************************************************************************
#include <iostream>
#include <cassert>
#include <stack>
using namespace std ;
int BinarySearch(int *A, int nTarget, int nLen);
// Find the longest decreasing sequence in array A of length nLen.
void FindLongestDecreasingSequence(int *A, int nLen)
{
int *index = new int[nLen];
int *LDS = new int[nLen];
index[0] = A[0];
LDS[0] = 1;
int indexLen = 1;
for (int i = 1; i < nLen; i++)
{
int pos = BinarySearch(index, A[i], indexLen);
index[pos] = A[i];
LDS[i] = pos + 1;
if(pos >= indexLen)
{
indexLen++;
}
}
int ResultLen = indexLen;
for (int i = nLen; i >= 0; i--)
{
if(LDS[i] == ResultLen)
{
index[ResultLen - 1] = A[i];
ResultLen--;
}
}
for (int i = 0; i < indexLen; i++)
{
cout << index[i] << " ";
}
delete [] index;
}
// Binary search nTarget in array A of length nLen.
int BinarySearch(int *A, int nTarget, int nLen)
{
assert(A != NULL && nLen > 0);
int start = 0;
int end = nLen - 1;
while (start <= end)
{
int mid = (start + end) / 2;
if(nTarget > A[mid])
{
end=mid-1;
}
else if(nTarget<A[mid])
{
start=mid+1;
}
else
{
return mid;
}
}
return start;
}
int main()
{
int A[] = {8, 14, 6, 2, 8, 14, 3, 2, 7, 4, 7, 2, 8, 101, 23, 6, 1, 2, 1, 1};
int nLen = sizeof(A) / sizeof(int);
FindLongestDecreasingSequence(A, nLen);
return 0;
}
// Output:
/*
14 8 7 6 2 1
*/
分享到:
相关推荐
分治思想:将难以直接求解的大问题分解为k个相同的子问题;对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止;
python算法-数组和链表 数组和链表.pdf
算法-数组排序 按数组内数字大小排序 取得最大值或最小值.rar
算法中数据结构的一个重要的应用,树状数组的两个应用。写的比较详尽
算法#26--查找字符串数组中最长的公共前缀Write a function to find the longest common prefix string
Giovanni Manzini and Paolo Ferragina 吸取了前人多种经验,结合n个算法,组建了最快的sa构建法.2005年新出的算法.是GNU开源项目,竞赛中 1000万的数据是 1 s,文件相当多,不能写在博客里,linux源码可以看: ...
学习笔记[韩顺平老师讲的数据结构和算法];数据结构和算法之稀疏数组。个人的一个理解。
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
使用C++实现最短子序列,对正在学习算法的同学应该挺有帮助的
华为od算法题-组装新的数组-Java解法
给定一个整形数组和一个数字s,找到数组中最短的一个连续子数组,使得连续子数组的数字和sum>=s,返回这个最短的连续子数组的长度值public int minS
C++求最长公共子序列!实用 花费了好长时间!!
设计分治法求一个数组中最大元素的位置,建立该算法的递推式并求解。
最长公共子序列的两种算法简介,一种是平时最常见的算法,还有一种用滚动数组来做的。
用递归算法编写求一个数组A中的最大元素;/****一个递归算法,求数组A中最大的元素***/ #include int Max(int A[], int i, int j) //求顺序表A中的最大元素 ……
C语言-《一维数组和冒泡算法》.ppt
本科算法实验-最长公共子序列【数据+代码+说明+流程图+测试用例】
这是一个有关算法的压缩包,里面包含二分算法、合并排序、最长公共子序列、最优装载、活动安排算法
数据结构实验报告--用简单数组实现下面各种排序算法