#Prefix Sum

Solutions This problem seem complicated if you try not using additional data structures. This is a typical case where pre-processing is needed and, in particular, we use two special kind of prefix sums. To answer to the first type of queries, we need to cache the running maximums of the prices: 1 2 3 4 5 6 7 8 vector<int> prefixMax(n); auto runningMax = p.front(); prefixMax[0] = runningMax; for (auto i=1; i<n; ++i) { prefixMax[i] = max(runningMax, p[i]); runningMax = prefixMax[i]; } In C++, we have a very useful standard algorithm to perform the same routine: [Read More]

Summer is over and people at Gugol are sad and unmotivated. They would prefer going back on vacation instead of working - how to blame them? Ted, head of employee happiness department, has got an idea to cheer people up: he will run a lottery among all the employees and will award the luckiest one with two extra weeks of vacation. The lottery will work this way: Ted will raffle off some ranges of employee ids like \( [120, 200] \) and \( [150, 180] \), a sophisticated algorithm will calculate which is the most frequent employee id in all such ranges, if more than one such an id exists, the sophisticated algorithm will select the smallest one - it corresponds to the employee who has been working at Gugol for more time You are a \( \cancel{slave} \) trainee at Gugol and you have to design and write such a sophisticated algorithm. [Read More]

Solutions We have two similar tasks: find the maximum sum of any nonempty subarray find the maximum sum of any nonempty subsequence The latter is clearly esier since the elements in a subsequence are not necessarily contiguous. The former is a very classical problem that we’ll deal with in a moment. To solve the first task, we can sum all the positive elements. This works as long as we have at least one positive (or zero) element. [Read More]