http://www.spoj.com/problems/HOTELS/
Here is an O(n) algorithm for you. Let us keep 3 variables P , Q and S. P and Q will show us an interval which we are considering at the moment and S will show the sum of the current interval. Initially P and Q are 1 and S is A[1]. Suppose he variable which shows the maximum purchase is called M. So now, if currently our S is smaller than M which means that there is still a chance that we might buy the next one as well, we increment Q by 1 meaning that we will be considering now the hotels between P and Q+1. If S is more then M which means that by taking the latest hotel we passed the limit so we increment P by 1 meaning that we are not taking the leftmost hotel. And also don't forget to update the answer in any step.
Here is an O(n) algorithm for you. Let us keep 3 variables P , Q and S. P and Q will show us an interval which we are considering at the moment and S will show the sum of the current interval. Initially P and Q are 1 and S is A[1]. Suppose he variable which shows the maximum purchase is called M. So now, if currently our S is smaller than M which means that there is still a chance that we might buy the next one as well, we increment Q by 1 meaning that we will be considering now the hotels between P and Q+1. If S is more then M which means that by taking the latest hotel we passed the limit so we increment P by 1 meaning that we are not taking the leftmost hotel. And also don't forget to update the answer in any step.
No comments:
Post a Comment