Thursday, 30 July 2015

HOTELS

Standard

Hotels Along the Croatian Coast

Link to the question :  HOTELS

HINT :

We apply the sliding concept. We start calculating the sum from index 0 of the array. If the sum exceeds the maximum amount given, we start subtracting  from sum from the beginning of the array, untill the sum becomes less than or equal to maximum amount.

SOURCE  CODE :


#include<stdio.h>
int main()
{
    int i, l;
    long long n, m, sum, max_sum;

    scanf("%lld%lld",&n, &m);

         int a[n];
        for(i=1; i<=n; i++)
        {
             scanf("%d", &a[i]);
        }
        l=1;
        max_sum = 0;
        sum = 0;
        for(i=1; i<=n; i++)
        {
            sum = sum + a[i];
            while(sum>m)
            {
                sum = sum - a[l];
                l++;
                if(max_sum<=sum && sum<=m)
                {
                    max_sum = sum;

                    break;
                }

            }
            if(max_sum<=sum && sum<=m)
            {
                max_sum = sum;

            }
        }
        printf("%lld\n", max_sum);

    return 0;
}

5 comments:

  1. Is there a need to break? while will itself end when sum<=m

    ReplyDelete
  2. You have a bug in your implementation. You start calculating the sum from index 1 whereas arrays in C begin at index 0.

    ReplyDelete
    Replies
    1. Yes, arrays begin with 0. But here I am not using the 0th index.

      Delete
  3. #include
    using namespace std;
    int main(){
    long long int n,m,max=0;
    cin>>n>>m;
    long long int a[n];
    long long int total=0,temp;
    long long int tot=0;
    long long int counter =0;
    for(long long int i=0;i>temp;
    tot+=temp;
    a[i]=temp;
    total+=temp;
    while(total>m){
    l:if(totaltot){
    cout<<tot;
    }else{
    cout<<max<<"\n";

    }

    }

    ReplyDelete