invoker._'s blog

Maximum sum :)
By invoker._, history, 2 years ago, In English

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

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please share the link to the question

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Extremely sorry, my approach does not work.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I don't think you should feel sorry, I was just trying to help you figure out why your approach does not work.

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sir with all due respect the Question you are asking is stack problem , Find maximum rectangle in a histogram , The assumption is that a[i]>=0

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry but I advice you to learn Descartes Tree.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply