#include <stdio.h>
#define N 9
//O(nlogn)
/**该方法可求最大上升子序列同时,可求最大不下降子序列
如{2,1,1,4}这种连续两个元素相等的序列,最大不下降子序列为{1,1,4}
*/
void lis1(int *a){
int i,j=0,temp,b[N],low,mid,high;
b[0]=a[0];
for(i=1;i<N;i++)
{
if(a[i]>=b[j]){
b[++j]=a[i];
}else{
low=0;high=j;
while(low<=high){
mid=(low+high)/2;
if(a[i]>b[mid]){
low=mid+1;
}else{
high=mid-1;
}
}
b[low]=a[i];
}
}
printf("LIS=%d",j+1);
}
//O(n^2)
/**
该方法在这一版本中不能求最大不下降子序列
同时也不是把下面代码中a[i]>a[j]修改为a[i]>=a[j]就可以这么简单
原因是跟这一解法的动态规划的状态转移方程有关,具体是怎么关系,没理解透
*/
void lis2(int *a){
int i,j=0,temp,b[N],max;
b[0]=1;//初始化,以a[0]结尾的最长递增子序列长度为1
for(i=1;i<N;i++)
{
b[i]=1;//b[i]最小值为1
for(j=0;j<i;j++)
if(a[i]>a[j]&&b[j]+1>b[i])
b[i]=b[j]+1;
}
for(max=i=0;i<N;i++){//求出整个数列的最长递增子序列的长度
if(b[i]>max)
max=b[i];
}
printf("max=%d",max);
}
void main(){
int a[]={3,1,4,2,5,7,6,8,9};
lis1(a);
lis2(a);
}
分享到:
相关推荐
leetcode04_寻找两个正序数组的中位数解法.rar !!!CSDN的一个特性: 即使我设置成免费下载,被下载的次数多了之后也会变成付C币下载的了,这个很头疼. !!!因此如果没有C币但想要下载的朋友可以在b站视频下留言给我,留下...
通过解法的探究可以实现程序的最优化,那么程序的质量便得到了最大化。
文件给出了四种方式求解子序列的最大和,并给出了具体的代码实现。对于深入探讨算法和程序性能非常有帮助。
主要介绍了Java编程数组中最大子矩阵简便解法实现代码,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下
算法系列之六:最长公共子序列(LCS)问题(连续子序列)的三种解法.doc
(编程之美P198-202)分析与解法根据题目的要求,求一维数组中的最长递增子序列,也就是找一个标号的序列b[0],b[1],…,b[m](0 <= b[0] < b[1] < … < b[m] < N),使得array[b[0]]<array[b[1]]<...
leetcode04_寻找两个正序数组的中位数解法.rar !!!CSDN的一个特性: 即使我设置成免费下载,被下载的次数多了之后也会变成付C币下载的了,这个很头疼. !!!因此如果没有C币但想要下载的朋友可以在b站视频下留言给我,留下...
解法1—O(N^2)解法 解法2—O(NlgN)解法 解法3—O(N)解法 可以直接在记事本运行
给定一个二分图G,在G的一个子图M中,M的...选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem) 如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。
通过了解树状数组的原理和定义来解决有关给定一个由n个不同的整数组成的序列,最少需要交换多少次交换相邻的两个数,使其升序排列。
假设有一数组(python里为list啦)[1,3,-3,4,-6,-1],求数组中最大连续子序列的和。例如在此数组中,最大连续子序列的和为5,即1+3+(-3)+4 = 5 2.O(n2)的解法 最简单粗暴的方式,双层循环,用一个maxsum标识最大...
关于连续子数组最大和这个问题,有两种解法,一种是动态规划 解法如下: function getMaxSubSum($arr){ $curSum = $arr[0]; $maxSum = $arr[0]; for($i = 1; $i < count($arr); $i++){ if
华为od算法题-组装新的数组-Java解法
约瑟夫环的数组解法
计算机算法设计与分析题目解答,最长公共子序列的动态规划解法
题面优化方法优化解法归类为贪心(每一步都是当前情况下的最优解,得到的就是最优解)把所有长度不同的递增最长子序列 的 结尾的最小值存到一个数组(q[])里面去,那
约瑟夫环问题的链表和数组两种解法 设有N个人围坐一圈并按顺时针方向从1到N编号,从第S个人开始进行1到M报数,报到第M个人时,此人出圈,再从他的下一个人重新开始1到M的报数,如此进行下去直到所有的人都出圈为止,...
Java数组随机不重复输出数组元素的不同解法,大家探讨。
数组的定义和特性 数组是Java中一种重要的数据结构,用于存储相同类型的元素,具有连续的内存空间和固定的容量。 数组的创建和初始化 在Java中,可以通过声明和赋值两种方式来创建和初始化数组,其中声明确定了数组...
1143. 最长公共子序列参考解法解法一:简单的动态规划直接用二位数组。优化二位动态数组用二个数组进行表示继续优化用以为数组进行表示。//代表dp[i - 1]