Блог пользователя invoker._

Maximum sum :)
Автор invoker._, история, 2 года назад, По-английски

So here is the problem

Let array A = { a1,a2,a3,...an} postitive integers

F(i,j) = min(ai,ai+1,....,aj) * (i-j+1);

Find the maximum value of F(i,j) for any I and J.

Example: A = {5,3,1,1}

(I = 1 J = 2) : SUM = 6

Example: A = {3,1,3,1,2}

(I = 1 J = 5) : SUM = 5

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you please share the link to the question

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm not sure I follow your code. What's your logic? And do you make any assumptions when breaking it to a sub-problem? Do you know why your code does not work for these counterexamples?

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sorry but I advice you to learn Descartes Tree.

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Descartes Tree is a binary tree satisfying the following requirements:

    • The id of each node satisfies the property of binary search tree.
    • The weight of each node satisfies the property of small-root heap.

    So after building it in $$$O(n)$$$ with monotonic queue ( I think you can search for tutorials online ), dfs it and find the size of every subtree so you can finish it without thinking.

    → Ответить
»
2 года назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

for every size of a subset let's find the maximum for a minimum of a subset in that size. we'll do that by adding the numbers one by one in decreasing order, an maintaining a set of all covered segments (segments that contain elements we've visited)

now when we update and get a new segment (by unifying the segments in both sides) we need to update all segments of size less or equal to that segment's size such that their answer is at least the current value.

we'll do that by maintaining an array of numbers arr: if the new segment is of size s and the element is of value x we do arr[s] = max(arr[s],x)

and after we add all the elements we loop and do:

for(int i = n; i; i --) {
    arr[i] = max(arr[i],arr[i+1]);
}

now we can just do:

int sol = 0;
for(int i = 1; i <= n; i ++) {
    sol = max(sol,arr[i]*i);
}

Edit: just remembered it's a pretty well known problem with a better solution: maintain a stack of the numbers and their positions, for each new number:

  • while the top of the stack has a bigger value, update the answer with it (maximize the answer with its value multiplied by the current index — the top's index) and delete it

  • add the number with the index to the stack.

in the end add -1 to the array to clear the stack and update everything.

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

One way of solve it is by for each index, find the index of the previous and next values that are lower than it, so you can calculate the max size of a range that has that value as minimum.

To do this:

  1. create a set with -1 and n

  2. sort the index by their values

  3. for each index in increasing order of values:

  • find the next and previous index using the set

  • update the global maximum using the result using the current index

  • add it to the set

If there are multiple indices with the same value, calculate the ranges of all of them before adding them to the range

→ Ответить