c++ - 最长双调子序列

Question

我正在尝试解决 Longest Bi tonic 子序列问题，尽管我从各个站点获得了运行代码，但我无法弄清楚为什么我的解决方案不起作用。我正在尝试返回最大长度子序列。我创建了一个名为数组的类型，它存储每个元素的值，如果它包含在升序子序列或降序子序列中。

#include <bits/stdc++.h>
#define li long int

int longestBitonicSubarray(int *input, int n) {
  li* output = new li[n];
  li* type = new li[n];
  output[0] = 1;
  type[0] = 0;
  /*
    type when 1 means order is ascending
    type when 2 means order is descending
    type when 0 not decided
  */
  for(li i=1;i<n;i++) {
    output[i] = 1;
    type[i] = 0;

    for(li j=i-1;j>=0;j--) {
      if(type[j] == 0 || type[j] == 1) {
        if(input[j] < input[i]) {
          li pos_ans = output[j] + 1;
          if(output[i] < pos_ans) {
            output[i] = pos_ans;
            type[i] = 1;
          }
        } else if(input[j] > input[i]) {
          li pos_ans = output[j] + 1;
          if(output[i] < pos_ans) {
            output[i] = pos_ans;
            type[i] = 2;
          }
        }
      } else {
        if(input[j] > input[i]) {
          li pos_ans = output[j] + 1;
          if(output[i] < pos_ans) {
            output[i] = pos_ans;
            type[i] = 2;
          }
        }
      }
    }
  }

  li ans = *max_element(output,output+n);
  delete [] output;
  delete [] type;
  return ans;
}

标签： c++