C++は、整数系列の最長インクリメントサブシーケンスの長さを計算します。

整数シーケンスを指定して、最も長いインクリメントサブシーケンスの長さを計算します。これは典型的な動的計画のアルゴリズムです。
例えば、8つの整数のシーケンス186 186 150 160 130 197 200は、最長のインクリメントサブシーケンスは150 160 197 200であり、長さは4である。
この問題を解決するには、この大きな問題を小さな問題に分解して、各数を順次考慮して、その数とその数の前のすべての数を含む最長インクリメントサブシーケンスの長さを計算し、算出した長さ値をその数の対応する値として記録して、最後にこの8個の数に対応する長さ値シーケンスを得ることができます。8個の数です。この8つの数の中の最大値を見つけたのは、すべての本の最長増分サブシーケンスの長さです。
あるいは、8個の数の最長のサブシーケンスの長さを計算するのは難しいと考えてもいいです。むしろ、最も簡単な場合を先に考えてください。一つの数だけの場合、一番長い増分のサブシーケンスの長さは1です。二つの数がある場合、最初の数とそれ以前の数だけを考慮して最長の増分サブシーケンスは1であり、第二の数を考慮すると、その前のすべての数の中で第二の数より小さいすべての数の中で最も長い増分サブシーケンスの長さの最大値を見つけてからプラスするだけで、第二の数の長さです。
実現コードを以下に示します。

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
int findLoogestIncreaseSeq(vector<int> &vect)
{
 int len = 0;
 int *count = new int[vect.size()];
 for (int i = 0; i < vect.size(); i++)
 count[i] = 1;
 for (int i = 0; i < vect.size(); i++)
 {
 for (int j = i - 1; j >= 0; j--)
 {
 if (vect[j] < vect[i] && count[j] >= count[i])
 {
 count[i] = count[j] + 1;
 }
 }
 if (count[i] > len)
 len = count[i];
 }
 delete [] count;
 return len;
}
int main()
{
 vector<int> vect;
 int temp;
 while (cin >> temp)
 {
 vect.push_back(temp);
 }
 cout << findLoogestIncreaseSeq(vect) << endl;
 return 0;
}

補足知識：C++は最長増分サブシーケンス（ダイナミック企画）を求めます。
i
0
1
2
3
4
5
6
7
8
a[i]
1
4
7
2
5
8
3
6
9
lis[i]
1
2
3
2
3
4
3
4
5
時間の複雑さはn^2のアルゴリズムです。

//        
//2019/2/28
#include<iostream>
using namespace std;
int LIS(int a[],int N)
{ 
 int lis[100] = {};
 for(int i =0;i<N;i++)//      lis    1
 {
  lis[i]=1; 
 }
 for(int i = 1;i<N;i++)
 {
  for(int j =0;j<i;j++)
  {
   if(a[j]<a[i]&&lis[j]<lis[i]+1) //              ，   lis 
    lis[i] = lis[j] + 1;
  }
 }
 int max = lis[0];
 for(int i =1;i<N;i++)
 {
  if(lis[i]>max)
   max = lis[i];   //  lis      ，           
 }
 return max;
}
int main()
{
 int N;
 int a[100];
 while(cin>>N)
 {
  for(int i = 0;i<N;i++)
   cin>>a[i];
  cout<<LIS(a,N)<<endl;
 }
 return 0;
}

以上のC++は整数シーケンスの最長増分のサブシーケンスの長さを計算します。つまり、小編集は皆さんのすべての内容に共有しています。参考にしてほしいです。どうぞよろしくお願いします。