递归计算数组中任意随机k个元素的最大和(无任何约束)

Question

找到数组中最多n个元素的最快方法是什么。(它们不需要是连续的(

例如a={1,3,2,5,0,10}

当n=2时，最大和将是15

例如，如果

• n为2，则我们将使用两个循环
• n是3，我们将使用3个循环，但是那就是O(n^3(

则对于n=4，5。。。迭代很难找到解决方案

我认为递归可以提供一个解决方案，所以我想出了

long rec(ArrayList<Int> a, int i, int n) {      
if (i > 0 && i< n) {
return Math.max(a.get(i), rec(a, i-1, m)+ a.get(i));

} else {
return a.get(0);
}
}

调用

for(int i = a.size() -1; i >=n; i--) {
long max = rec(a,i,n);

}

但我似乎看不到解决办法。对可能的算法或方法有什么建议吗？感谢

Answer 1

试图从时间复杂性的角度进行回答。假设输入阵列具有S个元素的大小。

1. 上述溶液与固定的"；最大值"；大小为n的数组存储所有的最大值

• 如果数组中的最大值排序到位，则使用
  二进制搜索进行搜索，以查看是否存在输入数组中的元素或应插入"；最大值"；数组具有平均复杂度O(log(n))。必须对输入数组，因此总平均复杂度为CCD_ 4。

• 如果最大值没有排序到位，则复杂性将为CCD_ 5，因为在最大值阵列中将存在线性搜索。

2. 使用堆的解决方案(https://en.wikipedia.org/wiki/Heap_(data_structure((，初始数组被加载到其中。在堆中加载元素是CCD_ 6。从堆中弹出最大值并重新构造堆为：~O(log(S))；做CCD_ 8次就是CCD_。因此，总复杂度为O(S)+O(n*log(S))

让我们使用一些实际大小来计算时间复杂性：

1. S=32, n=3, O(S*log(n))~32, O(S)+O(n*log(S))~47
2. S=32, n=5, O(S*log(n))~64, O(S)+O(n*log(S))~57
3. S=32, n=8, O(S*log(n))~96, O(S)+O(n*log(S))~72

因此，IMO，对于大型n，堆解决方案优于"；最大值数组"；一如果我们假设数组总是存储在堆中(即已经预加载在堆中(，那么堆解决方案总是更好的。