时间戳

首页 > 解决方案 > Maxsubsequence - 这个问题的关键见解是什么？

go - Maxsubsequence - 这个问题的关键见解是什么？

问题描述

下面是使用树递归方法的问题分配：

最大 子序列 一个数字的子序列是该数字的一系列（不一定是连续的）数字。例如，12345 的子序列包括 123、234、124、245 等。您的任务是获取低于某个长度的最大子序列。

def max_subseq(n, l):
    """
    Return the maximum subsequence of length at most l that can be found in the given number n.
    For example, for n = 20125 and l = 3, we have that the subsequences are
        2
        0
        1
        2
        5
        20
        21
        22
        25
        01
        02
        05
        12
        15
        25
        201
        202
        205
        212
        215
        225
        012
        015
        025
        125
    and of these, the maxumum number is 225, so our answer is 225.

    >>> max_subseq(20125, 3)
    225
    >>> max_subseq(20125, 5)
    20125
    >>> max_subseq(20125, 6) # note that 20125 == 020125
    20125
    >>> max_subseq(12345, 3)
    345
    >>> max_subseq(12345, 0) # 0 is of length 0
    0
    >>> max_subseq(12345, 1)
    5
    """
    "*** YOUR CODE HERE ***"

这个问题有两个关键的见解

我无法理解这个问题的见解，下面提到2点：

  1. 分为使用个位的情况和不使用的情况

  2. 在我们使用个位的情况下，您需要将数字放回末尾

我对这个问题的理解：

此问题的解决方案看起来生成所有子序列 upto l，伪代码如下所示：

digitSequence := strconv.Itoa(n) // "20125"

printSubSequence = func(digitSequence string, currenSubSequenceSize int) { // digitSequence is "20125" and currenSubSequenceSize is say 3
        printNthSubSequence(digitSequence, currenSubSequenceSize) + printSubSequence(digitSequence, currenSubSequenceSize-1)
    }

在哪里printNthSubSequence打印(20125, 3)或(20125, 2)等的子序列...

max_subseq在所有这些序列中找到然后变得容易

你能通过一个例子（比如20125, 1）帮助我理解这个问题中给出的见解吗？这是完整的问题

标签： gorecursiondivide-and-conquer

解决方案

像这样的东西？正如说明所建议的那样，尝试使用和不使用当前数字：

function f(s, i, l){
  if (i + 1 <= l)
    return Number(s.substr(0, l));

  if (!l)
    return 0;
    
  return Math.max(
    // With
    Number(s[i]) + 10 * f(s, i - 1, l - 1),
    // Without
    f(s, i - 1, l)
  );
}

var input = [
  ['20125', 3],
  ['20125', 5],
  ['20125', 6],
  ['12345', 3],
  ['12345', 0],
  ['12345', 1]
];

for (let [s, l] of input){
  console.log(s + ', l: ' + l);
  console.log(f(s, s.length-1, l));
  console.log('');
}

推荐阅读