Проблема с самой длинной возрастающей подпоследовательностью (leetcode)

ProgramBox

Проблема с самой длинной возрастающей подпоследовательностью (leetcode)

Post author:admin
Запись опубликована:11 апреля, 2023
Post category:Вопросы по программированию

#c #dynamic-programming

#c #динамическое программирование

Вопрос:

ссылка на проблему:

[ссылка]https://leetcode.com/problems/longest-increasing-subsequence /

 class Solution {
public:
int lengthOfLIS(vectoramp; nums)
{
int n=nums.size();
if (n==0)
return 0;

    int list[n];
    for(int i=0;i<n;i  )
        list[i]=0;
    
    list[0]=1;
    for(int i=1;i<n;i  )
    {
        for(int j=i-1;j>=0;j--)
        {
            if(nums[j]<nums[i])
                list[i]=max(list[i],1 list[j]);
        }
    }
    int ans=1;
    for(int i=0;i<n;i  )
        ans=max(ans,list[i]);
    return ans;
}
};

Ввод: [10,9,2,5,3,7,101,18]

вывод приближается: 3

ожидаемый результат: 4

не получается, где это неправильно.

1. Вы это отлаживали? Вы прошли через это шаг за шагом на бумаге? Теоретически, это должно просто занять время, а не знания…

2. @AsteroidsWithWings я выполнил все эти действия, я получаю 4 в качестве ответа, но компилятор говорит 3

3. Вопрос глупый, потому что, если вы ищете подпоследовательность, то по сути это должна быть непрерывная подпоследовательность. В любом случае, я не понимаю этого утверждения: list [i] = max(список [i], 1 список [j]); Вы должны инициализировать массив равным 1, заполнив все значения равными 1. Тонкий момент, который упускается, заключается в том, что для каждой подпоследовательности вы хотите проверить каждое значение, равное минимальному значению в подпоследовательности. Ниже я представил рабочее решение вместе с несколькими тестовыми примерами.

Ответ №1:

 #include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>

class Solution
{
public:
  int lengthOfLIS(std::vector<int> amp;);
  int max(int, int);
  std::string print(std::vector<int> const amp;);
};

int Solution::max(int a, int b)
{
  return a < b ? b : a;
}

std::string Solution::print(std::vector<int> const amp;input)
{
  std::stringstream ss;
    for (int i = 0; i < input.size(); i  )
        ss << input.at(i) << ' ';

  return ss.str();
}

int Solution::lengthOfLIS(std::vector<int> amp;nums)
{
  int n = nums.size();
  
  if (n == 0)
    return 0;

  int list[n];
  std::fill_n(list, n, 1);
  //list[0] = 1;

  for (int i = 1; i < n; i  )
  {
    int min_val = nums[i];

    for (int j = i - 1; j > -1; j--)
    {
      if (nums[j] < nums[i] amp;amp; nums[j] < min_val)
      {
        list[i]  ;
        min_val = nums[j];
      }
    }
  }

  int ans = 1;

  for(int i = 0; i < n; i  )
    ans = max(ans, list[i]);

  return ans;
}

int main()
{
  std::vector<int> Input0 { 10, 9, 2, 5, 3, 7, 101, 18 },
    Input1 { 10, 19, 2, 5, 3, 7, 101, 18 },
    Input2 { 10, 9, 12, 5, 3, 7, 101, 18 },
    Input3 { 10, 9, 2, 15, 3, 7, 101, 18 },
    Input4 { 10, 9, 2, 5, 13, 7, 101, 18 },
    Input5 { 10, 9, 2, 5, 3, 17, 101, 18 },
    Input6 { 10, 9, 2, 5, 13, 7, 10, 18 },
    Input7 { 10, 9, 2, 5, 13, 7, 101, 180 };
  Solution solution;
  std::cout << solution.print(Input0) << "t|t" << solution.lengthOfLIS(Input0) << std::endl;
  std::cout << solution.print(Input1) << "t|t" << solution.lengthOfLIS(Input1) << std::endl;
  std::cout << solution.print(Input2) << "t|t" << solution.lengthOfLIS(Input2) << std::endl;
  std::cout << solution.print(Input3) << "t|t" << solution.lengthOfLIS(Input3) << std::endl;
  std::cout << solution.print(Input4) << "t|t" << solution.lengthOfLIS(Input4) << std::endl;
  std::cout << solution.print(Input5) << "t|t" << solution.lengthOfLIS(Input5) << std::endl;
  std::cout << solution.print(Input6) << "t|t" << solution.lengthOfLIS(Input6) << std::endl;
  std::cout << solution.print(Input7) << "t|t" << solution.lengthOfLIS(Input7) << std::endl;
  return 0;
}

1. Спасибо, приятель, за все, но я хочу сказать это еще раз, я просто хочу найти ошибку в своем решении.

2. Этого теста if(nums[j]<nums[i]) недостаточно. Вам нужно проверить минимальное значение в каждой подпоследовательности. Вы также должны инициализировать список массивов на единицы, потому что для каждого элемента в последовательности существует по крайней мере одно значение, независимо от того, увеличивается или уменьшается последовательность. Функция lengthOfLIS строка за строкой совпадает с вашей, поэтому я надеюсь, вы понимаете, что я здесь описываю.

Ответ №2:

В вашем коде есть небольшая ошибка: каждый раз, когда вы обращаетесь к новому индексу (т. Е. на каждой итерации i), самая длинная возрастающая подпоследовательность, которую можно найти для индекса, — это сам этот элемент.

Итак, для каждой итерации изначально вы должны установить list[i] = 1

Или вы также можете инициализировать каждый элемент как 1 в массиве list.

 class Solution {
public:
    int lengthOfLIS(vector<int>amp; nums) {
        int n=nums.size();
        if (n==0)
            return 0;

        int list[n];
        for(int i=0;i<n;i  )
            list[i]=0;

        list[0]=1;
        for(int i=1;i<n;i  ) {
            list[i] = 1;
            for(int j=i-1;j>=0;j--) {
                if(nums[j]<nums[i])
                list[i]=max(list[i],1 list[j]);
            }
        }
        int ans=1;
        
        for(int i=0;i<n;i  )
            ans=max(ans,list[i]);
        return ans;
    }
};

Ответ №3:

Используя std::lower_bound , это прошло бы:

 #include <cstdint>
#include <vector>
#include <algorithm>

static const struct Solution {
    static const int lengthOfLIS(
        const std::vector<int> amp;nums
    ) {
        std::vector<int> longest;

        for (std::size_t index = 0; index < nums.size(); index  ) {
            const auto iter = std::lower_bound(longest.begin(), longest.end(), nums[index]);

            if (iter == longest.end()) {
                longest.emplace_back(nums[index]);

            } else {
                *iter = nums[index];
            }
        }

        return longest.size();
    }
};

Ссылки

Для получения дополнительной информации, пожалуйста, обратитесь к доске обсуждений, где вы можете найти множество хорошо объясненных принятых решений на различных языках, включая алгоритмы низкой сложности и асимптотический анализ времени выполнения / памяти^{1, 2}.