如果求最大非连续子序列??

假设有一个序列是L = [1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13]
他的最大非连续子序列就是 S = [1, 5, 7, 15, 13] 俩俩数字任意不相邻
现在要求给L求S

9个回答

public static List<Integer> longest_increasing_subsequence(List<Integer> sequence) {
    // Write your solution here
    if (sequence.isEmpty()) return new ArrayList<Integer>();
    int max_size[] = new int[sequence.size()];
    int prev_index[] = new int[sequence.size()];
    max_size[0] = 1;
    prev_index[0] = -1;
    for (int i = 1; i < sequence.size(); i++) {
        int cur_max = 1;
        int cur_prev = -1;
        int iVal = sequence.get(i);
        for (int j = i - 1; j >= 0; j--) {
            if (cur_max < max_size[j] + 1 && sequence.get(j) < iVal) {
                cur_max = max_size[j] + 1;
                cur_prev = j;
            }
        }
        prev_index[i] = cur_prev;
        max_size[i] = cur_max;
    }
    int max_idx = sequence.size() - 1;
    int max_val = max_size[max_idx];
    for (int i = max_idx - 1; i >= 0; i--) {
        if (max_val < max_size[i]) {
            max_idx = i;
            max_val = max_size[i];
        }
    }
    List<Integer> aList = new ArrayList<Integer>();
    int idx = max_idx;
    aList.add(sequence.get(idx));
    while (prev_index[idx] >= 0) {
        idx = prev_index[idx];
        aList.add(sequence.get(idx));
    }
    List<Integer> retList = new ArrayList<Integer>(aList.size());
    for (int i = aList.size() - 1; i >= 0; i--) {
        retList.add(aList.get(i));
    }
    return retList;
}
feelcycle_07
默默悟问 回复weixin_42042460: 已经答了
一年多之前 回复
weixin_42042460
weixin_42042460 回复feelcycle_07: 我开了个新问题,你试出来了可以来答
一年多之前 回复
feelcycle_07
默默悟问 回复weixin_42042460: 应该可以,回头我试下
一年多之前 回复
weixin_42042460
weixin_42042460 可以用分治法吗,我再开个新的
一年多之前 回复
feelcycle_07
默默悟问 以为是求最大升序数列了
一年多之前 回复
public static String[] getMaxSubArray(int[] arr) {
        String[] strArr = new String[arr.length];
        for(int i =0;i<arr.length;i++) {
            strArr[i] = String.valueOf(arr[i]);
        }
        for(int i=2;i<arr.length;i++) {
            if (arr[i-2] + arr[i] > arr[i-1]) {
                arr[i] = arr[i-2] + arr[i];
                strArr[i] = strArr[i-2]+","+strArr[i];
            } else {
                arr[i] = arr[i-1];
                strArr[i] = strArr[i-1];
            }
        }
        return strArr[strArr.length-1].split(",");
    }

weixin_42042460
weixin_42042460 回复flonny: 这个能用分治来做吗
一年多之前 回复
flonny
精锐小菜鸡 回复weixin_42042460: 的确,我直接跳过了前两个参数,是有点问题,我再优化一下吧。
一年多之前 回复
weixin_42042460
weixin_42042460 你的结果是2,8 正确的应该是5,8
一年多之前 回复
weixin_42042460
weixin_42042460 arr={5,2,1,8}
一年多之前 回复
weixin_42042460
weixin_42042460 这个可以的,可以把字符串数组换成list来存吗?
一年多之前 回复
flonny
精锐小菜鸡 两个数组,一个做int的sum运算和对比,另一个做字符串拼接
一年多之前 回复

状态转移方程:dp[i]=max(dp[i-1],dp[i-2]+dp[i])

weixin_42042460
weixin_42042460 这个是求最大值的,如何记录每个数呢
一年多之前 回复

用动态规划来解,具体代码实现参考:https://www.jianshu.com/p/04c03059e538

改造很简单:

private static boolean isValueNotNextInArray(List<Integer> sequence, int ival, int cur_prev, int[] prev_index) {
    while(cur_prev >= 0) {
        int prev_val = sequence.get(cur_prev);
        if (Math.abs(ival - prev_val) == 1) return false;
        cur_prev = prev_index[cur_prev];
    }
    return true;
}

public static List<Integer> longest_notnext_subsequence(List<Integer> sequence) {
    // Write your solution here
    if (sequence.isEmpty()) return new ArrayList<Integer>();
    int max_size[] = new int[sequence.size()];
    int prev_index[] = new int[sequence.size()];
    max_size[0] = 1;
    prev_index[0] = -1;
    for (int i = 1; i < sequence.size(); i++) {
        int cur_max = 1;
        int cur_prev = -1;
        int iVal = sequence.get(i);
        for (int j = i - 1; j >= 0; j--) {
            if (cur_max < max_size[j] + 1 && isValueNotNextInArray(sequence, iVal, j, prev_index)) {
                cur_max = max_size[j] + 1;
                cur_prev = j;
            }
        }
        prev_index[i] = cur_prev;
        max_size[i] = cur_max;
    }
    int max_idx = sequence.size() - 1;
    int max_val = max_size[max_idx];
    for (int i = max_idx - 1; i >= 0; i--) {
        if (max_val < max_size[i]) {
            max_idx = i;
            max_val = max_size[i];
        }
    }
    List<Integer> aList = new ArrayList<Integer>();
    int idx = max_idx;
    aList.add(sequence.get(idx));
    while (prev_index[idx] >= 0) {
        idx = prev_index[idx];
        aList.add(sequence.get(idx));
    }
    List<Integer> retList = new ArrayList<Integer>(aList.size());
    for (int i = aList.size() - 1; i >= 0; i--) {
        retList.add(aList.get(i));
    }
    return retList;
}

public static void testLongArray() {
List vals = longest_notnext_subsequence(Arrays.asList(1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13));
System.out.println(vals);
}

public static void main(String args[]) {
testLongArray();
}

结果是:
[0, 5, 2, 7, 9, 15, 13]

你假定的结果不正确。

示例:C#
static List GetMaxSeq(List list)
{
List res = new List();
List ou = new List();
List qi = new List();
for (int i = 0; i < list.Count; i++)
{
if (i%2==0) //奇偶分裂,奇偶数列都是连续不相邻的
{
ou.Add(list[i]);
}
else
{
qi.Add(list[i]);
}
}
int last = 0;
for (int i = 0; i < qi.Count; i++)
{
if (ou[i] {
ou[i] = qi[i]; // 在相等位置上将奇列中大于偶列中的数替换到偶列
last = i;
}
}
for (int i = 0; i {
if (i!=last+1) // 记录最后的替换位置,防止替换后结果连续,那么即排除奇最后位+1的偶数,在原数列奇偶相等时还需判断是否超索引
{
res.Add(ou[i]);
}
}
return res;
}
static void OutList(List list)
{
string res = "";
foreach (T item in list)
{
res += item + " ";
}
Console.WriteLine(res);
}
static int[] InPutToArr(string line)
{
string[] nums=line.Split(',');
int[] res=new int[nums.Length ];
for (int i = 0; i < nums.Length; i++)
{
res[i] = int.Parse(nums[i]);
}
return res;
}
static void Main(string[] args)
{
string line = Console.ReadLine();
while (!line.Trim().Contains("quit"))
{
int[] arr = InPutToArr(line);
List input = new List(arr);
List output = GetMaxSeq(input);
OutList(output);
line = Console.ReadLine();
}
//string line = "1,0,5,3,2,7,9,15,6,4,13";

Console.ReadLine();
}
图片说明

weixin_42042460
weixin_42042460 回复weixin_39521929: 我会再开一个问题,你的qq多少
一年多之前 回复
weixin_39521929
以伽利略之名 回复weixin_42042460: 没漏的,不知哪里漏了,你是完全不懂代码的吗,我怎么重发给你,你给个啥QQ,微信邮件联系方式,我发源码给你
一年多之前 回复
weixin_42042460
weixin_42042460 代码有的地方漏了吧,能发个有格式的嘛
一年多之前 回复
 public static Integer[] getMaxSubArray(int[] arr) {
        List<Integer> list = new ArrayList<Integer>();
        int index = 0;
        do {
            list.add(arr[index]);
            if(index+2 >= arr.length)
                break;
            if(index+2 < arr.length && index+3 >= arr.length) {
                list.add(arr[index+2]);
                break;
            }
            if(arr[index+2] >= arr[index+3])
                index += 2;
            else
                index += 3;
        } while(index<arr.length);

        Integer[] resultArray = new Integer[list.size()];
        list.toArray(resultArray);
        return resultArray;
    }
weixin_42042460
weixin_42042460 回复flonny: 问题就是dp只能求出最大和,不能求出每个数字把
一年多之前 回复
flonny
精锐小菜鸡 回复weixin_42042460: 好吧,的确是要用动态规划:dp[i] = max(dp[i-2]+dp[i], dp[i-1])
一年多之前 回复
weixin_42042460
weixin_42042460 0,100,5,3,2,7,9,15这个就错了,你这个是首先把第一项加进去吧,如果第二项比第一个大呢?
一年多之前 回复

被你的描述迷惑了,这个应该没问题了:
public static List longest_maxval_subsequence(List sequence) {
// Write your solution here
if (sequence.isEmpty()) return new ArrayList();
int max_vals[] = new int[sequence.size()];
int prev_index[] = new int[sequence.size()];
max_vals[0] = sequence.get(0);
prev_index[0] = -1;
for (int i = 1; i < sequence.size(); i++) {
int cur_max = sequence.get(i);
int cur_prev = -1;
int iVal = sequence.get(i);
for (int j = i - 2; j >= 0; j--) {
if (cur_max < max_vals[j] + iVal) {
cur_max = max_vals[j] + iVal;
cur_prev = j;
}
}
prev_index[i] = cur_prev;
max_vals[i] = cur_max;
}
int max_idx = sequence.size() - 1;
int max_val = max_vals[max_idx];
for (int i = max_idx - 1; i >= 0; i--) {
if (max_val < max_vals[i]) {
max_idx = i;
max_val = max_vals[i];
}
}
List aList = new ArrayList();
int idx = max_idx;
aList.add(sequence.get(idx));
while (prev_index[idx] >= 0) {
idx = prev_index[idx];
aList.add(sequence.get(idx));
}
List retList = new ArrayList(aList.size());
for (int i = aList.size() - 1; i >= 0; i--) {
retList.add(aList.get(i));
}
return retList;
}

feelcycle_07
默默悟问 回复weixin_42042460: 这个就是动态规划
一年多之前 回复
weixin_42042460
weixin_42042460 你这个是分治法?
一年多之前 回复
feelcycle_07
默默悟问 List<Integer> vals = longest_maxval_subsequence(Arrays.asList(1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13)); System.out.println(vals);
一年多之前 回复
feelcycle_07
默默悟问 回复feelcycle_07: List模版带Integer的,系统没显示出来
一年多之前 回复
feelcycle_07
默默悟问 输出是:[1, 5, 7, 15, 13]
一年多之前 回复
public static String[] getMaxSubArray(int[] arr) {
        String[] strArr = new String[arr.length];
        for(int i =0;i<arr.length;i++) {
            strArr[i] = String.valueOf(arr[i]);
        }
        for(int i=1;i<arr.length;i++) {
            if(i<2) {
                if (arr[i-1] > arr[i]) {
                    arr[i] = arr[i - 1];
                    strArr[i] = strArr[i-1];
                }
                continue;
            }
            if (arr[i-2] + arr[i] > arr[i-1]) {
                arr[i] = arr[i-2] + arr[i];
                strArr[i] = strArr[i-2]+","+strArr[i];
            } else {
                arr[i] = arr[i-1];
                strArr[i] = strArr[i-1];
            }
        }
        return strArr[strArr.length-1].split(",");
}

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
分治法求最大非连续子序列
-
最大连续子序列 问题
-
求一个序列的最大子序列。
-
求解第k个最大递增子序列?
-
c语言编译的最大子序列求和问题
-
java 求最大子序列和问题递归求解报越界异常
-
求区间最长不下降子序列
-
序列计算连续最大积,怎么使用C语言的程序编写代码方式有效加以实现的
-
求出最大的连续递增的子序列的问题,如何才能使用C语言的编程技术来进行代码的编写的过程
-
Oracle有关取序列问题
-
动态规划求最长公共子序列,存在多个解时只能输出一个。
-
用python计算括号匹配序列最长公共子序列的问题?
-
A sequence of numbers 序列的问题
-
Java实现:最长上升子序列LIS算法
-
这种时间序列预测问题用哪种神经网络比较合适呀
-
算出这个数组中某一段连续元素的积的最大值,怎么采用C语言的程序的编写的过程的实现的步骤
-
求助大神:c语言求最长公共子序列问题
-
怎么用Java实现:单调递增子序列(动态规划)
-
怎么在建表的时候用外键联系dept表 序列插入值不够怎么办
-
程序员竟然钟爱这个!我 low了
今天和一帮程序员大佬群里闲聊(需要入群的可以加最底下微信哦~)聊着聊着竟然扯到鞋子一直在讨论穿什么鞋子比较耐脏然后一帮大佬集中围殴小白鞋说小白鞋虽然百搭但是太容易脏,太不...
程序员实用工具网站
目录 1、搜索引擎 2、PPT 3、图片操作 4、文件共享 5、应届生招聘 6、程序员面试题库 7、办公、开发软件 8、高清图片、视频素材网站 9、项目开源 10、算法 11、在线工具宝典大全 程序员开发需要具备良好的信息检索能力,为了备忘(收藏夹真是满了),将开发过程中常用的网站进行整理。 1、搜索引擎 1.1、秘迹搜索 一款无敌有良心、无敌安全的搜索引擎,不会收...
996下的程序员,该如何保证自己的身体健康?
作者:陈大鱼头github:KRISACHAN自从开始写代码之后,一天里大部分的时间都贡献了给了电脑跟那张从X总办公室里搬回来的人体工学椅了。鱼头也经历过无数次的 肥胖 ...
史上最详细的IDEA优雅整合Maven+SSM框架(详细思路+附带源码)
网上很多整合SSM博客文章并不能让初探ssm的同学思路完全的清晰,可以试着关掉整合教程,摇两下头骨,哈一大口气,就在万事具备的时候,开整,这个时候你可能思路全无 ~中招了咩~ ,还有一些同学依旧在使用eclipse或者Myeclipse开发,我想对这些朋友说IDEA 的编译速度很快,人生苦短,来不及解释了,直接上手idea吧。这篇文章每一步搭建过程都测试过了,应该不会有什么差错。本文章还有个比较优秀的特点,就是idea的使用,基本上关于idea的操作都算是比较详细的,所以不用太担心不会撸idea!最后,本文
全球最厉害的 14 位程序员!
来源 | ITWorld 整理自网络全球最厉害的 14 位程序员是谁?今天就让我们一起来了解一下吧,排名不分先后。01. Jon Skeet个人名望:程序技术问答网站 S...
我花了一夜用数据结构给女朋友写个H5走迷宫游戏
起因 又到深夜了,我按照以往在csdn和公众号写着数据结构!这占用了我大量的时间!我的超越妹妹严重缺乏陪伴而 怨气满满! 而女朋友时常埋怨,认为数据结构这么抽象难懂的东西没啥作用,常会问道:天天写这玩意,有啥作用。而我答道:能干事情多了,比如写个迷宫小游戏啥的! 当我码完字准备睡觉时:写不好别睡觉! 分析 如果用数据结构与算法造出东西来呢? ...
招人!入职阿里仅1年,我和做AI的程序员薪资翻了2倍!
最近在知乎上,关于AI的这个话题又被顶起来,其中,这条回答让人印象深刻:在这短短的一条信息里,无疑显示出:AI行业缺人,高端岗位80万年薪恐怕也招不来!小编上周在一个AI...
什么是大公司病(太形象了)
点击蓝色“五分钟学算法”关注我哟加个“星标”,天天中午 12:15,一起学算法作者 | 南之鱼来源 | 芝麻观点(chinamkt)所谓大企业病,一般都具有机构臃肿、多重...
让程序员崩溃的瞬间(非程序员勿入)
今天给大家带来点快乐,程序员才能看懂。 来源:https://zhuanlan.zhihu.com/p/47066521 1. 公司实习生找 Bug 2.在调试时,将断点设置在错误的位置 3.当我有一个很棒的调试想法时 4.偶然间看到自己多年前写的代码 5.当我第一次启动我的单元测试时 ...
Spring高级技术梳理
Spring高级技术梳理 序言正文SpringDate部分Spring全家桶之SpringData——预科阶段Spring全家桶之SpringData——Spring 整合Hibernate与Hibernate JpaSpring全家桶之SpringData——Spring Data JPASpring全家桶之SpringData——SpringData RedisSpringBoot部分Sp...
Git 天天用 但是 Git 原理你了解吗?
Git 原理 做技术一定要知其然知其所以然,意思就是:知道它是这样的,更知道它为什么是这样的。我主要通过4块内容来简单介绍 Git 是原理是什么样的。这4块内容如下: Git 存储目录结构介绍 Git 是如何存储的 Git 的对象 Git引用 当然 Git 原理不仅仅包含这些,想要更深入了解请查看官方教程 https://git-scm.com/book/zh/v2/。 本文内容是我在 Git...
Android——微信自动回复实现
首先本文的测试微信版本是7.0.3 ,亲测可以使用。 需要实现-抓取微信自动回复消息的功能点。 一.首先打开DDMS,使用按钮。 在微信中回复一个消息 点击Stop Method Profiling。 二.查看生成的报表,观察到如下两个方法 其中1应该是发送消息的接口方法。2应该是UI层显示的方法。 三.首先分析第一个方法: 1.,可以看到,参数值是String,返...
分享靠写代码赚钱的一些门路
作者 mezod,译者 josephchang10如今,通过自己的代码去赚钱变得越来越简单,不过对很多人来说依然还是很难,因为他们不知道有哪些门路。今天给大家分享一个精彩...
对计算机专业来说学历真的重要吗?
我本科学校是渣渣二本,研究生学校是985,现在毕业五年,校招笔试、面试,社招面试参加了两年了,就我个人的经历来说下这个问题。 这篇文章很长,但绝对是精华,相信我,读完以后,你会知道学历不好的解决方案,记得帮我点赞哦。 先说结论,无论赞不赞同,它本质就是这样:对于技术类工作而言,学历五年以内非常重要,但有办法弥补。五年以后,不重要。 目录: 张雪峰讲述的事实 我看到的事实 为什么会这样 ...
技术人员要拿百万年薪,必须要经历这9个段位
很多人都问,技术人员如何成长,每个阶段又是怎样的,如何才能走出当前的迷茫,实现自我的突破。所以我结合我自己10多年的从业经验,总结了技术人员成长的9个段位,希望对大家的职...
8000字干货:那些很厉害的人是怎么构建知识体系的
本文约8000字,正常阅读需要15~20分钟。读完本文可以获得如下收益: 分辨知识和知识体系的差别 理解如何用八大问发现知识的连接点; 掌握致用类知识体系的构建方法; 能够应用甜蜜区模型找到特定领域来构建知识体系。 1. 知识体系?有必要吗? 小张准备通过跑步锻炼身体,可因为之前听说过小腿变粗、膝盖受伤、猝死等等与跑步有关的意外状况,有点担心自己会掉进各种坑里,就在微信上问朋友圈一直晒跑步...
万字长文!线性代数的本质课程笔记完整合集
点击上方“Datawhale”,选择“星标”公众号第一时间获取价值内容系列目录1.向量究竟是什么https://www.bilibili.com/video/av5987...
Java 网络爬虫,就是这么的简单
这是 Java 网络爬虫系列文章的第一篇,如果你还不知道 Java 网络爬虫系列文章,请参看 学 Java 网络爬虫,需要哪些基础知识。第一篇是关于 Java 网络爬虫入门内容,在该篇中我们以采集虎扑列表新闻的新闻标题和详情页为例,需要提取的内容如下图所示: 我们需要提取图中圈出来的文字及其对应的链接,在提取的过程中,我们会使用两种方式来提取,一种是 Jsoup 的方式,另一种是 httpcli...
nginx学习,看这一篇就够了:下载、安装。使用:正向代理、反向代理、负载均衡。常用命令和配置文件
文章目录前言一、nginx简介1. 什么是 nginx 和可以做什么事情2.Nginx 作为 web 服务器3. 正向代理4. 反向代理5. 动静分离6.动静分离二、Nginx 的安装三、 Nginx 的常用命令和配置文件四、 Nginx 配置实例 1 反向代理五、 Nginx 配置实例 2 负载均衡六、 Nginx 配置实例 3 动静分离七、 Nginx 的高可用集群 前言 一、nginx简介...
Java 爬虫遇上数据异步加载,试试这两种办法!
这是 Java 爬虫系列博文的第三篇,在上一篇 Java 爬虫遇到需要登录的网站,该怎么办? 中,我们简单的讲解了爬虫时遇到登录问题的解决办法,在这篇文章中我们一起来聊一聊爬虫时遇到数据异步加载的问题,这也是爬虫中常见的问题。 现在很多都是前后端分离项目,这会使得数据异步加载问题更加突出,所以你在爬虫时遇到这类问题不必惊讶,不必慌张。对于这类问题的解决办法总体来说有以下两种: 1、内置一个浏览器内...
Angular 入门教程系列:39:使用ng-alain进行开发
在前面的文章中介绍过ng-alain,当时在使用的时候还显得不是很方便,最简单的一个demo运行的都不是非常流畅。而目前的版本已经做有较大的改进,再这个基础上进行二次开发,尤其是一些后端的平台或者监控的平台看起来都比较不错。在这篇文章中继续来确认一下使用的感受。
相关热词 c# 增加元素 c#控制台简单加法 c# 服务端框架 c# 判断事件是否注册 c#中is和has c# udp 连接超时 c#词典 c#实现排列组合 c# oss 上传 c#判断输入的是否为ip

相似问题

1
分治法求最大非连续子序列
13
c语言编译的最大子序列求和问题
5
最大子序列求和问题为什么这个程序输出不来结果 输入数字显示为空
1
有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13……求出这个数列的前n项之和?
2
一棵非空的二叉树的先序序列和后续序列正好相同,则该二叉树一定满足?
0
最佳连续的子序列数的计算问题,采用C语言如何实现解决?
0
C程序输出题目所要求的序列,序列中每个元素一行。如果存在两个符合要求的序列
0
区间数组连续最大序列问题怎么利用C语言的办法编写代码来实现的??
0
最大二进制公共子序列的一个算法的问题如何利用C语言的办法去实现怎么做?
0
查找最大的非递减的序列的一个算法的问题采用C语言进行解答
0
寻找非递减的子序列的一个算法问题,采用C语言的技术实现的方式是?
1
子集序列的最大连续值问题的算法,如何利用C语言的方式编程来实现
0
两个连续子序列的匹配的问题,利用C语言的办法怎么实现的呢?
2
以实际数量求平均值。编程输出该平均值序列,采用C语言编程实现
0
最大的二进制子序列的查找算法,运用C语言的程序的设计的原理实现
0
序列上截取一个最大的和的连续数列的问题,怎么采用C程序的语言设计的办法
0
请问这个程序用c怎么写?什么时候输出的序列不是单调递增?
2
使用phtread多线程编程程序来生成Fibonacci序列 c/c++
0
mysql按规律自定义序列生成
0
最大优雅的子序列的和的数据结构的设计,怎么采用C语言的程序编写思想的解决的过程?