1
$\begingroup$

Problem

Hello everybody! The above problem is a combinatorics problem I got wrong. :( This is ZIO $2006$, P$1$.

For the first part, I got as answer: $3$ which is wrong. What I did to try my value which I guessed was trial and error combined with the observations I made at every step. Notice that in the first sub-case, days 8 to 15 sum to $0$ and days 1 through 7 sum to 0. I got the maximum via days 10 through 14 which I thought would be the answer. After noting the answer to be $4$, I began my search for it by expanding to the west because the east has just a -1 which is useless. 3-4 = -1 hmm not useful and we move on, -1 + 2 = 1 that is still less, 1-1 = 0 which is even lesser and continuing. But because they (1 through 7) sum to $0$, the max sum is no more.

Also note that this way would be way longer and unexpected for the longer sub-cases (b) and (c) (provided that you're are given about 10 minutes for each sub-part). I researched and found out that there is something called a window-sliding technique but unfortunately it's for coders and this is a pen and paper exam. Although, I am pretty sure this question is either me just being so dumb or a silly.

The answers are $4,4,6$ respectively.

I would appreciate some easy to understand and easy to think-of in an exam solutions although they may be long and not the most elegant.

Any help would be appreciated. Thanks!

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Make a 3rd row with the cumulative sum, e.g., for the 1st example, $$\matrix{1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\cr-1&3&-2&2&-2&1&-1&2&-4&2&-1&3&-2&1&-1\cr-1&2&0&2&0&1&0&2&-2&0&-1&2&0&1&0\cr}$$ The smallest number in the 3rd row is $-2$ in column $9$, then the largest number after that is $2$ in column $12$, so days $10$ to $12$ inclusive yielded a profit of $2-(-2)=4$, the maximum.

$\endgroup$
9
  • 1
    $\begingroup$ Note to OP: this isn't guaranteed to give the maximum, but if you modify it slightly it will work (i.e. how could it not work as currently stated? Can you add a step at the end to let you loop through the argument again to definitely find the max?) $\endgroup$
    – Brian Moehring
    Commented Nov 8, 2019 at 21:36
  • $\begingroup$ @Brian you might also want to have a look at math.stackexchange.com/questions/3425541/… $\endgroup$
    – Gerry Myerson
    Commented Nov 9, 2019 at 3:00
  • 1
    $\begingroup$ @Vasu090 Take a simple example where the earnings for consecutive days are $$-1, 4, -5, 2$$ Then the cumulative sum would be $$-1, 3, -2, 0$$ so the smallest number would be $-2$ on day 3, the largest number after that is $0$ on day 4, but $0-(-2) = 2$ is not the maximum, since we earned $4$ on day 2. However, if you treat the above as one step, remove day 3 and every day after it, you get $$-1, 3$$ as your new sequence of cumulative sums, and then reapplying the above procedure to get a second candidate of $3 - (-1) = 4,$ which is what we wanted. $\endgroup$
    – Brian Moehring
    Commented Nov 9, 2019 at 6:08
  • 1
    $\begingroup$ This "correction" is still not the way we solve this type of problem in practice (worst case complexity is now $O(n^2)$) but it might be what you come up with in a pinch. With this algorithm in mind, however, you probably can remove the redundant steps and find the $O(n)$ algorithm (if you want to investigate this, my hint is to consider "running max/min" from each direction) $\endgroup$
    – Brian Moehring
    Commented Nov 9, 2019 at 6:14
  • 2
    $\begingroup$ @Vasu090 There's some ambiguity, so let me restate it. Calculate the cumulative sum, find the minimum value at day $d,$ find the maximum on days after day $d$, find the difference of these values and write this number down. Now do the same procedure using only the days previous to day $d$ (days $1$ through $d-1$ inclusive). Repeat until there are no more days in the range you're considering. $\endgroup$
    – Brian Moehring
    Commented Nov 9, 2019 at 6:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .