tôi đang cố gắng để giải quyết những câu dưới đây:dãy dài nhất mà tăng đầu tiên sau đó giảm
Một chuỗi trong đó giá trị của các yếu tố giảm đầu tiên và sau đó tăng được gọi là V-Sequence. Trong một V-Sequence hợp lệ, cần có ít nhất một phần tử trong phần tử giảm dần và ít nhất một phần tử trong nhánh tăng. Ví dụ: "5 3 1 9 17 23" là một chuỗi V hợp lệ có hai phần tử trong nhánh giảm là 5 và 3 và 3 phần tử trong nhánh tăng là 9, 17 và 23. Nhưng không có chuỗi nào "6 4 2" hoặc "8 10 15" là V-Sequence vì "6 4 2" không có phần tử nào trong phần tăng lên trong khi "8 10 15" không có phần tử trong phần giảm.
Một chuỗi con của chuỗi được lấy bằng cách xóa 0 hoặc nhiều phần tử khác khỏi chuỗi. Ví dụ: định nghĩa "7", "2 10", "8 2 7 6", "8 2 7 10 6" v.v ... là các chuỗi con hợp lệ của "8 2 7 10 6"
Cho một dãy số N tìm chuỗi phụ dài nhất của nó, đó là một chuỗi V-Sequence.
Tôi hiện đang có một O (n^2) giải pháp trong đó đầu tiên tôi khởi tạo một mảng (m []) sao cho mỗi m [i] chứa các chuỗi tăng dài nhất bắt đầu từ 'i' trong mảng.
Tương tự, tôi khởi tạo một mảng khác (d []), sao cho mỗi d [i] chứa chuỗi giảm dài nhất ENDING tại điểm đó.
Cả hai hoạt động lấy O (n^2)
bây giờ tôi đi qua các mảng và chọn giá trị lớn nhất của m [i] + d [i] -1, như vậy mà điều kiện cần được thỏa mãn.
Điều tôi muốn biết là - Có giải pháp O (n lg n) không ?? Bởi vì giải pháp của tôi không chạy trong giới hạn thời gian yêu cầu. Cảm ơn bạn :)
Mã sản phẩm:
#include<cstdio>
#include<algorithm>
using namespace std;
int m[ 200000 ];
int d[200000 ];
int n;
int arr[200000 ];
void LIS()
{
m[ n-1 ] = 1;
int maxvPos = -1;
int maxv = -1;
for(int i=n-2; i>=0; i--)
{
maxv = -1;
for(int j=i+1; j<n; j++)
{
if((m[j]+1 > maxv) && (arr[i] < arr[j]))
{
maxv = m[j]+1;
maxvPos = j;
}
}
if(maxv>0)
{
m[i] = maxv;
}
else
m[i ] = 1;
}
}
void LDS()
{
d[0] = 1;
int maxv = -1;
int maxvPos = -1;
for(int i=1; i<n; i++)
{
maxv = -1;
for(int j=i-1; j>=0; j--)
{
if((d[j]+1 > maxv) && arr[j]>arr[i])
{
maxv = d[j]+1;
maxvPos = j;
}
}
if(maxv>0)
d[i] = maxv;
else
d[i]=1;
}
}
int solve()
{
LIS();
LDS();
int maxv = 0;
int curr = 0;
for(int i=0; i<n; i++)
{
curr = d[i] + m[i] -1 ;
if((d[i]>0) && (m[i]>0))
{
if(curr != 1)
maxv = max(curr, maxv);
}
}
return maxv;
}
/* static void printArr(int[] a)
{
for(int i : a)
System.out.print(i + " ");
System.out.println();
} */
int main()
{
scanf("%d", &n);
for(int i=0; i<n; i++)
{
scanf("%d", &arr[i]);
}
printf("%d\n", solve());
return 0;
}
Đó là từ một cuộc thi lập trình diễn ra tối qua. Bài gửi của tôi đã vượt quá thời gian cho 6 trong số 11 trường hợp kiểm tra. – arya