Search This Blog

Friday, February 2, 2018

Maximum movies watched

Alex and Tom share a common passion for movies, but unfortunately they do not really like each other. A movie festival is taking place in another town, and both of them want to participate in it. The problem is the neither of them is willing to meet the other during the event.

After some not very pleasant negotiations, they agree that the fairest way to fulfill both goals is to pick two intervals of time so as to maximize the total number of movies that they can both see on their own. Keeping in mind that Alex and Tom each want to spend several days in a row at the festival(as the town in which the event is taking place is not close by, so they do not want to travel there more than once), help them count the maximal number of movies that can be seen by both of them independently.

int getMaxMoviesWatched(int[] movies, int K, int L)

movies is an array of size N which specifies the number of movies on each day of the festival
K is the number of days for Alex
L is the number of days for Tom

Assume N is an integer within the range of [2,600]
K and L are integers within the range [1,N-1]
Each element of array movies is an integer within the range [1,500]

return the maximal number of movies that can be seen by both of them or -1 if a solution is not possible.

Examples:

movies = [6, 1, 4, 6, 3, 2, 7, 4], K = 3, L = 2

Alex can participate 4+6+3 = 13 movies
Tom                          7+4 = 11 movies

Return 13+11=24

movies = [10, 19, 15], K=2, L=2

Return -1

My Solution: (Might be wrong, please advice) 


  static int getMaxMoviesWatched(int[] movies, int K, int L){
    int length = movies.length;
    if ( length < K+L )
      return -1;

    int maxK = 0;
    int indK = 0;
    for(int i = 0; i <= length-K; i++){
      int value = 0;
      for(int j = i; j < K+i; j++)
        value += movies[j];

      if ( value > maxK ){
        maxK = value;
        indK = i;
      }
    }

    int maxL = 0;
    for(int i = 0; i <= length-L; i++){
      int value = 0;
      if( i == indK )
        i += K;

      for(int j = i; j < L+i; j++)
        value += movies[j];

      if ( value > maxL ){
        maxL = value;
      }
    }

    return maxK + maxL;

  }


No comments:

Post a Comment