Run Code  | API  | Code Wall  | Misc  | Feedback  | Login  | Theme  | Privacy  | Patreon 

maximum nights you can accommodate

/* #20 Maximum Number of Nights You Can Accommodate
Given a set of numbers in an array which represent number of consecutive nights of AirBnB 
reservation requested, as a host, pick the sequence which maximizes the number of days of occupancy, 
at the same time, leaving at least 1 day gap in between bookings for cleaning. 
Problem reduces to finding max-sum of non-consecutive array elements.
*/

#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

int maxNights(vector<int>& v) {
    if(v.size()<1) return 0;
    if(v.size()==1) return v[0];
    int f1 = 0; 
    int f2 = v[0];
  
    for(int i = 1; i<v.size(); i++){
        int f = max(f1+v[i], f2); 
        f1 = f2;
        f2 = f; 
    }
    return f2;
}

int main() {
    vector<int> v = {1, 2, 3, 3};
    int res = maxNights(v);
    cout << res << endl;
    assert( res == 5); 
    return 0;
}
 run  | edit  | history  | help 0