Maxsubsequence-此问题的主要见解是什么? [英] Maxsubsequence - What are the key insights for this problem?

问题描述

以下是使用树递归方法的问题分配:

Below is the problem assignment using tree recursion approach:

最大子序列数一个数字的子序列是该数字的一系列(不一定是连续的)数字.例如，12345的子序列包括123、234、124、245等.您的任务是使最大子序列低于特定长度.

Maximum Subsequence A subsequence of a number is a series of (not necessarily contiguous) digits of the number. For example, 12345 has subsequences that include 123, 234, 124, 245, etc. Your task is to get the maximum subsequence below a certain length.

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 ***"

---

此问题有两个关键见解

---

There are two key insights for this problem

• 您需要分为两种情况:使用"1"的数字和不使用"1"的数字.在这种情况下，我们要减少 l ，因为我们使用了数字之一，而在没有数字的情况下我们就不使用.
• 在使用位数的情况下，您需要将数字放回末尾，并在数字 n的末尾附加数字 d 是 10 * n + d .

• You need to split into the cases where the ones digit is used and the one where it is not. In the case where it is, we want to reduce l since we used one of the digits, and in the case where it isn't we do not.
• In the case where we are using the ones digit, you need to put the digit back onto the end, and the way to attach a digit d to the end of a number n is 10 * n + d.

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

I could not understand the insights of this problem, mentioned below 2 points:

1. 分为使用数字和不使用数字的情况

如果我们使用的是一位数字，则需要将数字放回末尾

---

我对这个问题的理解:

---

My understanding of this problem:

此问题的解决方案看起来可以生成直至 l 的所有子序列，伪代码如下:

Solution to this problem looks to generate all subsequences upto l, pseudo code looks like:

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)等的子序列...

where printNthSubSequence prints subsequences for (20125, 3) or (20125, 2) etc...

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

Finding max_subseq among all these sequences then becomes easy

您能举例说明(例如 20125，1 )来帮助我理解有关此问题的见解吗?此处是完整的问题

Can you help me understand the insights given in this problem, with an example(say 20125, 1)? here is the complete question

推荐答案

是这样的吗?如说明所示，请尝试使用当前数字和不使用当前数字:

Something like this? As the instructions suggest, try it with and without the current digit:

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('');
}

这篇关于Maxsubsequence-此问题的主要见解是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！