假设有一个序列是L = [1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13]
他的最大非连续子序列就是 S = [1, 5, 7, 15, 13] 俩俩数字任意不相邻
现在要求给L求S
如果求最大非连续子序列??
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
9条回答
- 默默悟问 2018-04-22 15:33关注
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; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 素材场景中光线烘焙后灯光失效
- ¥15 请教一下各位,为什么我这个没有实现模拟点击
- ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来
- ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
- ¥20 有关区间dp的问题求解
- ¥15 多电路系统共用电源的串扰问题
- ¥15 slam rangenet++配置
- ¥15 有没有研究水声通信方面的帮我改俩matlab代码
- ¥15 ubuntu子系统密码忘记
- ¥15 保护模式-系统加载-段寄存器