c++ - 确定一个数组是否可以分成两个子序列，每个子序列的顺序都是递增的

Question

我目前正在为我的算法课做作业。指令摘要:

用户输入一个整数“n”来确定测试用例的数量。 用户单独输入另一个整数“num”以确定每个测试用例中元素的数量。 用户输入单个数组的元素。

算法必须处理数组并确定它是否可以划分为两个子序列，每个子序列都严格递增。如果结果是肯定的，程序打印"is"，否则打印“否”。

我有 24 小时的时间来完成这项任务，但我正在努力解决主要问题 - 我无法正确处理用户输入。 (想出一个算法来拆分两个子序列)

更新:我找到了这个解决方案。它通过了 4/5 测试，但在最后一次测试中未达到时间限制。

#include<iostream>
#include<string>
using namespace std;

bool run(){
int numbers;
int *arr;
cin >> numbers;
arr = new int[numbers];

for (int i = 0; i < numbers; i++)
cin >> arr[i];

long long int MAX = 0;
long long int MAX2 = 0;
string stra = "";
string strb = "";
string result = "";
string total = "";

long long int sum = 0;

for (int i = 0; i < numbers; i++){
if (arr[i] >= MAX && arr[i] != arr[i - 1]){
    stra += to_string(arr[i]);
    MAX = arr[i];
}

else
    if (arr[i] >= MAX2 && MAX2 != MAX){
    strb += to_string(arr[i]);
    MAX2 = arr[i];
    }
}

for (int i = 0; i < numbers; i++){
result = to_string(arr[i]);
total += result;
}

long long int len1 = stra.length();
long long int len2 = strb.length();

sum += len1 + len2;

delete[] arr;

if (sum != total.length())
return false;
else
   return true;
 }

int main()
{
int test;
cin >> test;

while (test > 0)
{
if (run())
    cout << "Yes\n";
else
    cout << "No\n";
test--;
}
system("pause");
}

示例输入:

2

5

3 1 5 2 4

5

4 8 1 5 3

示例输出: 是的 否

解释:对于数组 3 1 5 2 4，两个严格递增的子序列是:3 5 和 1 2 4。

Answer 1

似乎存在至少三个元素的任何相等或递减子序列意味着数组不能分成两个子序列，每个子序列都严格递增，因为一旦我们将第一个元素放在一部分中，第二个元素在另一部分，我们没有地方放置第三个。

这似乎表明找到最长递减或相等子序列是一个确定的解决方案。因为我们只需要长度为 3 的一个，所以如果每个元素的左边有一个更大或相等的元素，我们可以在 O(n) 中记录它。然后执行相反的操作。如果任何元素在左侧有一个更大或相等的伙伴，在右侧有一个更小或相等的伙伴，则答案为“否”。

我们可以通过沿值和位置绘图来可视化 O(n) 时间、O(1) 空间方法:

                          A  choosing list B here
           A              x   would be wrong
           x
value               B        z
^              B    x
|              x
| A          
| x
|    
|    B
|    x
- - - - - - - -> position

我们注意到，一旦建立了第二个列表(第一次减少)，到目前为止任何高于绝对最大值的元素都必须分配给包含它的列表，而任何低于它的元素都可以在任何情况下，如果有的话，只放在第二个列表中。

如果我们要将一个高于绝对最大值的元素分配给第二个列表(不包含它)，我们可以通过使下一个元素低于我们刚刚插入的元素来任意构造假阴性第二个列表和前一个绝对最大值，但大于第二个列表的前一个最大值(图中的 z)。如果我们正确地将高于先前绝对最大值的元素插入到第一个列表中，我们仍然有空间将新的任意元素插入到第二个列表中。

(下面的 JavaScript 代码在技术上使用 O(n) 空间来显示分区，但请注意我们只依赖于每个部分的最后一个元素。)

function f(A){
  let partA = [A[0]];
  let partB = [];
  
  for (let i=1; i<A.length; i++){
    if (A[i] > partA[partA.length-1])
      partA.push(A[i]);
    else if (partB.length && A[i] <= partB[partB.length-1])
      return false;
    else
      partB.push(A[i]);
  }
  return [partA, partB];
}

let str = '';
let examples = [
  [30, 10, 50, 25, 26],
  [3, 1, 5, 2, 4],
  [4, 8, 1, 5, 3],
  [3, 1, 1, 2, 4],
  [3, 4, 5, 1, 2],
  [3, 4, 1],
  [4, 1, 2, 7, 3]
];

for (e of examples)
  str += JSON.stringify(e) + '\n' + JSON.stringify(f(e)) + '\n\n';

console.log(str);