Algorithm
problem link- https://www.spoj.com/problems/HOTELS/
HOTELS - Hotels Along the Croatian Coast
There are N hotels along the beautiful Adriatic coast. Each hotel has its value in Euros.
Sroljo has won M Euros on the lottery. Now he wants to buy a sequence of consecutive hotels, such that the sum of the values of these consecutive hotels is as great as possible - but not greater than M.
You are to calculate this greatest possible total value.
Input
In the first line of the input there are integers N and M (1 ≤ N ≤ 300 000, 1 ≤ M < 231).
In the next line there are N natural numbers less than 106, representing the hotel values in the order they lie along the coast.
Output
Print the required number (it will be greater than 0 in all of the test data).
Example
input5 12 2 1 3 4 5output 12 |
![]() |
input4 9 7 3 5 6output 8 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
using namespace std;
int main(){
long long n,m;
scanf("%lld%lld",&n,&m);
long long a[n];
for(long long i=0;i<n;i++){
scanf("%lld",&a[i]);
}
long long maxi=0;
long long temp=a[0];
long long start=0;
long long i;
for(i=1;i<=n;i++){
while(temp>m&&start<i-1){
temp-=a[start];
start++;
}
maxi=max(maxi,temp);
temp+=a[i];
}
printf("%lld\n",maxi);
return 0;
}
Copy The Code &
Try With Live Editor
Input
2 1 3 4 5
Output
Demonstration
SPOJ Solution-Hotels Along the Croatian Coast-Solution in C, C++, Java, Python