最長下降しないシーケンスnlognアルゴリズム
O(nlogn)のアルゴリズムの鍵は配列temp[]を確立することであり、temp[i]は長さiの下降しないシーケンスの末尾要素の最小値を表し、topは配列の現在の長さを表し、アルゴリズムが完了した後のtopの値は最長の下降しないサブシーケンスの長さである.
現在求められている長さをtopとするとnum[i]とtemp[top]:
1.num[i]>=temp[top]、すなわちnum[i]がtop長のシーケンスの最後の要素より大きい場合、シーケンスの長さを1、すなわちtop++増加させ、現在のtemp[top]=num[i]にすることができる.
2.num[i]の場合
現在求められている長さをtopとするとnum[i]とtemp[top]:
1.num[i]>=temp[top]、すなわちnum[i]がtop長のシーケンスの最後の要素より大きい場合、シーケンスの長さを1、すなわちtop++増加させ、現在のtemp[top]=num[i]にすることができる.
2.num[i]の場合
#include
#define SIZE 1001
using namespace std;
int main()
{
int i, j, n, top, temp;
int stack[SIZE];
cin >> n;
top = 0;
/* 0 */
stack[0] = -1;
for (i = 0; i < n; i++)
{
cin >> temp;
/* */
if (temp > stack[top])
{
stack[++top] = temp;
}
else
{
int low = 1, high = top;
int mid;
/* >=temp */
while(low <= high)
{
mid = (low + high) / 2;
if (temp > stack[mid])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
/* temp */
stack[low] = temp; // temp
}
}
/* */
cout << top << endl;
//system("pause");
return 0;
}
lower_bound ：
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int main()
{
int stack[1005];
int n,top=0,temp;
cin>>n;
stack[0]=-1;
for(int i=0;i>temp;
if(temp>=stack[top])
stack[++top]=temp;
else
{
int loc=lower_bound(stack,stack+top,temp)-stack; // >=temp ，