当前位置:首页 > 题解目录 > 正文内容

【题解】最小子序列

【题目描述】

给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。

如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和最大 的子序列。

与子数组不同的地方在于,「数组的子序列」不强调元素在原数组中的连续性,也就是说,它可以通过从数组中分离一些(也可能不分离)元素得到。

注意,题目数据保证满足所有约束条件的解决方案是 唯一 的。同时,返回的答案应当按 非递增顺序 排列。

【输入描述】

包含一行,每个数用空格隔开。

【输出描述】

包含一行,满足条件的子序列。每个数用空格隔开。

【样例1输入】

4 3 10 9 8

【样例1输出】

10 9

【样例1解释】

子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。

【样例2输入】

4 4 7 6 7

【样例2输出】

7 7 6

【样例2解释】

子序列 [7,7] 的和为 14 ,不严格大于剩下的其他元素之和(14 = 4 + 4 + 6)。因此,[7,6,7] 是满足题意的最小子序列。注意,元素按非递增顺序返回。

【提示】

  • 1 <= nums.length <= 500

  • 1 <= nums[i] <= 100

本篇文章已加密,请输入密码后查看。

扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

八皇后问题

八皇后问题

【题目描述】八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行...

CSPJ2022 乘方

【题目描述】小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数a和b,求ab的值是多少。ab即 b 个a相乘的值,例如23 即为3个2相乘,结果为2×2×2=8。“简单!”小...

2020CSPJ-直播获奖

【题目描述】NOI2130 即将举行。为了增加观赏性,CCF 决定逐一评出每个选手的成绩,并直播即时的获奖分数线。本次竞赛的获奖率为w%,即当前排名前 w% 的选手的最低成绩就是即时的分数线...

【算法】最少步数

【算法】最少步数

【题目描述】在各种棋中,棋子的走法总是一定的,如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性,因此,他规定马既能按“日”走,也能如象一样走“田”字。他的同桌平时喜欢下围棋,知...

【题解】开关灯(1)

【题目描述】假设有N盏灯(N为不大于5000的正整数),从1到N按顺序依次编号,初始时全部处于开启状态;有M个人(M为不大于N的正整数)也从1到M依次编号。第一个人(1号)将灯全部关闭,第二个人(2号...

【题解】求车速问题

【题目描述】一辆以固定速度行驶的汽车,司机在上午10点看到里程表上的读数是一个对称数(即这个数从左向右读和从右向左读是完全一样的),为95859。两小时后里程表上出现了一个新的对称数。问该车的速度是多...