Maximum Value taken by thief

问题:

Consider we have a sacks of gold and thief wants to get the maximum gold. Thief can take the gold to get maximum by,

1) Taking the Gold from contiguous sacks.

2) Thief should take the same amount of gold from all sacks.

N Sacks 1 <= N <= 1000

M quantity of Gold 0 <= M <= 100

Sample Input1:

3 0 5 4 4 4

Output: 16

Explanation: 4 is the minimum amount he can take from the sacks 3 to 6 to get the maximum value of 16.

Sample Input2: 2 4 3 2 1

Output: 8

Explanation: 2 is the minimum amount he can take from the sacks 1 to 4 to get the maximum value of 8.

I approached the problem using subtracting the values from array and taking the transition point from negative to positive, but this doesn't solves the problem.

EDIT: code provided by OP to find the index:

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; 
    } 
} 

回答1:

The best amount of gold (TBAG) taken from every sack is equal to weight of some sack. Let's put indexes of candidates in a stack in order.

When we meet heavier weight (than stack contains), it definitely continues "good sequence", so we just add its index to the stack.

When we meet lighter weight (than stack top), it breaks some "good sequences" and we can remove heavier candidates from the stack - they will not have chance to be TBAG later. Remove stack top until lighter weight is met, calculate potentially stolen sum during this process.

Note that stack always contains indexes of strictly increasing sequence of weights, so we don't need to consider items before index at the stack top (intermediate AG) in calculation of stolen sum (they will be considered later with another AG value).

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 

Every item is pushed and popped once, so linear time and space complexity.

P.S. I feel that I've ever seen this problem in another formulation...

回答2:

I see two differents approaches for the moment :

Naive approach: For each pair of indices (i,j) in the array, compute the minimum value m(i,j) of the array in the interval (i,j) and then compute score(i,j) = |j-i+1|*m(i,j). Take then the maximum score over all the pairs (i,j).

-> Complexity of O(n^3).

Less naive approach:

1. Compute the set of values of the array

2. For each value, compute the maximum score it can get. For that, you just have to iterate once over all the values of the array. For example, when your sample input is [3 0 5 4 4 4] and the current value you are looking is 3, then it will give you a score of 12. (You'll first find a value of 3 thanks to the first index, and then a score of 12 due to indices from 2 to 5).

3. Take the maximum over all values found at step 2.

-> Complexity is here O(n*m), since you have to do at most m times the step 2, and the step 2 can be done in O(n).

Maybe there is a better complexity, but I don't have a clue yet.