algorithm - 以最佳方式减少序列

Question

我们得到一个 a 序列，其中包含 n 个数字。序列 a 的减少定义为替换元素 a[i] 和 a[i+1]使用 max(a[i],a[i+1])。

每个缩减操作都有一个定义为 max(a[i],a[i+1]) 的成本。经过n-1归约后得到长度为1的序列。

现在我们的目标是打印给定序列 a 的最佳缩减成本，使得长度为 1 的结果序列具有最小成本。

例如:

1

2

3

Output :

5

O(N^2) 的解决方案是微不足道的。有什么想法吗？

编辑1: 人们问我的想法，所以我的想法是成对地遍历序列，并为每一对检查成本，最后减少成本最低的对。

1 2 3
 2 3     <=== Cost is 2

所以将上面的序列减少到

2 3

现在再次遍历序​​列，我们得到成本为 3

2 3
 3       <=== Cost is 3

所以总成本是2+3=5

以上算法是O(N^2)。这就是为什么我要求一些更优化的想法。

Answer 1

O(n) 解决方案:

高级:

基本思想是重复合并小于其邻居 ns 和 nl 的任何元素 e 与其最小的邻居 ns 。这产生了最小的成本，因为合并的成本和结果都是 max(a[i],a[i+1])，这意味着没有合并可以使元素比当前更小，因此，e 最便宜的可能合并是 ns，并且该合并不会增加任何其他可能合并的成本。

这可以通过单遍算法来完成，方法是将数组中的元素堆栈按降序排列。我们将当前元素与其两个相邻元素(一个位于堆栈顶部)进行比较，并执行适当的合并，直到完成。

伪代码:

stack = empty
for pos = 0 to length
  // stack.top > arr[pos] is implicitly true because of the previous iteration of the loop
  if stack.top > arr[pos] > arr[pos+1]
    stack.push(arr[pos])
  else if stack.top > arr[pos+1] > arr[pos]
    merge(arr[pos], arr[pos+1])
  else while arr[pos+1] > stack.top > arr[pos]
    merge(arr[pos], stack.pop)

Java代码:

Stack<Integer> stack = new Stack<Integer>();
int cost = 0;
int arr[] = {10,1,2,3,4,5};
for (int pos = 0; pos < arr.length; pos++)
  if (pos < arr.length-1 && (stack.empty() || stack.peek() >= arr[pos+1]))
    if (arr[pos] > arr[pos+1])
      stack.push(arr[pos]);
    else
      cost += arr[pos+1]; // merge pos and pos+1
  else
  {
    int last = Integer.MAX_VALUE; // required otherwise a merge may be missed
    while (!stack.empty() && (pos == arr.length-1 || stack.peek() < arr[pos+1]))
    {
      last = stack.peek();
      cost += stack.pop(); // merge stack.pop() and pos or the last popped item
    }
    if (last != Integer.MAX_VALUE)
    {
      int costTemp = Integer.MAX_VALUE;
      if (!stack.empty())
        costTemp = stack.peek();
      if (pos != arr.length-1)
        costTemp = Math.min(arr[pos+1], costTemp);
      cost += costTemp;
    }
  }
System.out.println(cost);