Find maximum possible value of advertising | C ++ program for the above approach ; Function to find maximum possible advertising value ; To store advertising value at i - th minute ; Base Case ; If no advertisement is taken on ith minute ; If advertisement is taken on i - th minute ; Driver 's Code ; array [ ] [ 0 ] start time array [ ] [ 1 ] advertising value
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE int max_value ( int array [ ] [ 2 ] , int M , int K , int N ) { int time [ M ] = { 0 } ; for ( int i = 0 ; i < N ; i ++ ) { time [ array [ i ] [ 0 ] ] = array [ i ] [ 1 ] ; } int dp [ M ] [ 2 ] ; dp [ 0 ] [ 0 ] = 0 ; dp [ 0 ] [ 1 ] = time [ 0 ] ; for ( int i = 1 ; i < M ; i ++ ) { dp [ i ] [ 0 ] = max ( dp [ i - 1 ] [ 0 ] , dp [ i - 1 ] [ 1 ] ) ; dp [ i ] [ 1 ] = time [ i ] ; if ( i - K >= 0 ) { dp [ i ] [ 1 ] += max ( dp [ i - K ] [ 0 ] , dp [ i - K ] [ 1 ] ) ; } } return max ( dp [ M - 1 ] [ 0 ] , dp [ M - 1 ] [ 1 ] ) ; } int main ( ) { int array [ ] [ 2 ] = { { 0 , 10 } , { 4 , 110 } , { 5 , 30 } } ; int N = 3 ; int K = 4 ; int M = 6 ; cout << max_value ( array , M , K , N ) ; }