Во-первых, вы хотите иметь возможность вычислять самую длинную монотонную подпоследовательность из одной точки в другую.(Увеличивается или уменьшается, это не сильно влияет на проблему.) Для этого вы можете использовать динамическое программирование.Например, чтобы решить задачу с указанными индексами от 0 до i, вы начинаете с решения задачи от 0 до 0 (тривиально!), Затем от 0 до 1, затем от 0 до 2 и т. Д. При каждой записи (вмассив) ваше лучшее решение.
Например, вот код на python для вычисления самой длинной неубывающей последовательности, идущей от индекса 0 до индекса i.Мы используем массив (bbest) для хранения решения от 0 до j для всех j от 0 до i: длина самой длинной неубывающей подпоследовательности от 0 до j.(Используется стратегия динамического программирования.)
def countasc(array,i):
mmin = array[0] # must start with mmin
mmax= array[i] # must end with mmax
bbest=[1] # going from 0 to 0 the best we can do is length 1
for j in range(1,i+1): # j goes from 1 to i
if(array[j]>mmax):
bbest.append(0) # can't be used
continue
best = 0 # store best result
for k in range(j-1,-1,-1): # count backward from j-1 to 0
if(array[k]>array[j]) :
continue # can't be used
if(bbest[k]+1>best):
best = bbest[k]+1
bbest.append(best)
return bbest[-1] # return last value of array bbest
или эквивалентно в Java (предоставляется по запросу):
int countasc(float[] array,int i) {
float mmin = array[0];
float mmax = array[i];
ArrayList<Integer> bbest= new ArrayList<Integer>();
bbest.add(1);
for (int j = 1; j<=i;++j) {
if(array[j]>mmax){
bbest.add(0);
continue;
}
int best = 0;
for(int k = j-1; k>=0;--k) {
if(array[k]>array[j])
continue;
if(bbest.get(k).intValue()+1>best)
best = bbest.get(k).intValue()+1;
}
bbest.add(best);
}
return bbest.get(bbest.size()-1);
}
Вы можете написать функцию такого же типа, чтобы найти самую длинную не- возрастающая последовательность от i до n-1 (оставлено как упражнение).
Обратите внимание, что countasc работает за линейное время.
Теперь мы можем решить актуальную проблему:
Start with S, an empty array
For i an index that goes from 0 to n-1 :
compute the length of the longest increasing subsequence from 0 to i (see function countasc above)
compute the length of the longest decreasing subsequence from n-1 to i
add these two numbers, add the sum to S
return the max of S
Имеет квадратичную сложность.Я уверен, что вы можете улучшить это решение.В этом подходе много избыточности.Например, для скорости вам, вероятно, не следует повторно вызывать countasc с неинициализированным массивом bbest: его можно вычислить один раз.Возможно, вы сможете снизить сложность до O (n log n), проделав еще больше работы.