-
Notifications
You must be signed in to change notification settings - Fork 0
/
minimum-subsequence-in-non-increasing-order_1403.py
32 lines (21 loc) · 1.66 KB
/
minimum-subsequence-in-non-increasing-order_1403.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Given the array nums, obtain a subsequence of the array whose sum of elements is strictly greater than the sum of the non included elements in such subsequence.
# If there are multiple solutions, return the subsequence with minimum size and if there still exist multiple solutions, return the subsequence with the maximum total sum of all its elements. A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array.
# Note that the solution with the given constraints is guaranteed to be unique. Also return the answer sorted in non-increasing order.
# Example 1:
# Input: nums = [4,3,10,9,8]
# Output: [10,9]
# Explanation: The subsequences [10,9] and [10,8] are minimal such that the sum of their elements is strictly greater than the sum of elements not included. However, the subsequence [10,9] has the maximum total sum of its elements.
# Example 2:
# Input: nums = [4,4,7,6,7]
# Output: [7,7,6]
# Explanation: The subsequence [7,7] has the sum of its elements equal to 14 which is not strictly greater than the sum of elements not included (14 = 4 + 4 + 6). Therefore, the subsequence [7,6,7] is the minimal satisfying the conditions. Note the subsequence has to be returned in non-decreasing order.
# ---------------------------------------Runtime 69 ms Beats 63.39% Memory 16.4 MB Beats 51.45%---------------------------------------
# Time Complexity O(n2)
from typing import List
class Solution:
def minSubsequence(self, nums: List[int]) -> List[int]:
sortedNum, output = sorted(nums), []
while True:
output.append(sortedNum.pop())
if sum(output) > sum(sortedNum):
return output