Алгоритм требуется для этой задачи?

Question

Входные данные: n (int) а также n ценности (float), которые представляют обменные курсы (различные между ними) со случайным значением между 4 а также 5.

Выход: Вычислить максимальное количество значений, которые можно использовать (в том же порядке), чтобы представить восходящую, а затем нисходящую кривую?

---

Ex восемь значений

4.5 4.6 4.3 4.0 4.8 4.4 4.7 4.1

должен вывозить

5 (4.5 4.6 4.8 4.4 4.1)

---

Мой подход

• Если я попробую последовательно ifS, я получаю случайный массив, который уважает условие кривой, но не самый длинный.
• Я не пробовал возвращаться, потому что я не так знаком с этим, но что -то подсказывает мне, что мне нужно вычислить все решения с ним, а затем выбрать самые длинные.
• И, наконец,: грубая сила, но, поскольку это задание для дизайна алгоритма; Я также могу не передать это. :)

Есть ли более простой/более эффективный/более быстрый метод?

Вот моя попытка, основанная на алгоритме Даниэля Лемира. Кажется, это не учитывает позиции 0, i и n. Я уверен, что если я могу их исправить?

for(int i = 0; i<n-1; i++){
            int countp=0;   // count ascending
            int countn=0;   // count descending
            for(int j=0;j<=i;j++){
                    if(currency[j]<currency[j+1]){
                        countp++;
                        System.out.print(j+" ");
                    }
                }
            System.out.print("|| ");
            for(int j=i;j<n-1;j++){
                if(currency[j]>currency[j+1]){
                    countn++;
                    System.out.print(j+" ");
                }
            }
        System.out.println();
        if(countn+countp>maxcount) maxcount=countn+countp;                   
        }

Answer 1

Во -первых, вы хотите иметь возможность вычислить самую длинную монотонную последовательность из одной точки в другую. (Независимо от того, увеличивается ли это или уменьшается, не сильно влияет на проблему.) Чтобы сделать это, вы можете использовать динамическое программирование. Например, чтобы решить проблему с учетом индексов от 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) с еще большей работой.

Answer 2

Первый шаг - понять, как решить связанные Самое длинное увеличение подпоследовательности проблема. Для этой проблемы есть Простой алгоритм то есть O(n^2) хотя Оптимальный алгоритм является O(n log n). Анкет Понимание этих алгоритмов должно поставить вас на правильный путь к решению.