algorithm - 小偷拿走的最大值

Question

假设我们有一袋金子，小偷想得到最多的金子。小偷可以拿走金币以获取最大的 yield ，

1) 从连续麻袋中取出黄金。

2) 小偷应该从所有麻袋中拿走相同数量的黄金。

N 个麻袋 1 <= N <= 1000

M 数量的黄金 0 <= M <= 100

示例输入 1:

3 0 5 4 4 4

输出:16

解释:4 是他从麻袋 3 到 6 中拿走的最小数量，以获得最大值 16。

示例输入 2:2 4 3 2 1

输出:8

解释:2 是他从麻袋 1 到 4 中拿走的最小数量，以获得最大值 8。

我通过从数组中减去值并采用从负到正的过渡点来解决问题，但这并不能解决问题。

编辑:OP 提供的用于查找索引的代码:

int temp[6]; 
for(i=1;i<6;i++){ 
    for(j=i-1; j>=0;j--) { 
        temp[j] = a[j] - a[i]; 
    } 
} 
for(i=0;i<6;i++){ 
    if(temp[i]>=0) { 
        index =i; 
        break; 
    } 
} 

Answer 1

从每个麻袋中取出的黄金 (TBAG) 的最佳数量等于某个麻袋的重量。让我们按顺序将候选人的索引放在堆栈中。

当我们遇到更重的权重(比堆栈包含的)时，它肯定会继续“良好序列”，因此我们只需将其索引添加到堆栈即可。

当我们遇到更轻的权重(比堆栈顶部)时，它会打破一些“好的序列”，我们可以从堆栈中删除更重的候选者——他们以后将没有机会成为 TBAG。移除堆栈顶部直到满足更轻的重量，计算在此过程中可能被盗的金额。

注意堆栈总是包含权重严格递增序列的索引，因此我们在计算被盗金额时不需要考虑堆栈顶部索引之前的项目(中间AG)(稍后将考虑它们与另一个AG值).

for idx in Range(Sacks):
     while (not Stack.Empty) and (Sacks[Stack.Peek] >= Sacks[idx]): //smaller sack is met
         AG = Sacks[Stack.Pop]
         if Stack.Empty then
            firstidx = 0
         else  
            firstidx = Stack.Peek + 1
         //range_length * smallest_weight_in_range
         BestSUM = MaxValue(BestSUM, AG * (idx - firstidx))  
     Stack.Push(idx)

now check the rest: 
  repeat while loop without >= condition 

每个项目都被插入和弹出一次，所以线性时间和空间复杂度。

附言我觉得我曾经在另一个公式中看到过这个问题......