Q49 Highway BillBoards - Coding Ninjas Codestudio (approach 1 LIS)

PHOTO EMBED

Fri Mar 31 2023 06:04:39 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07

import java.util.* ;
import java.io.*; 
 
public class Solution {

	public static int highwayBillboard(int[] billboards, int[] revenue, int m, int x) {
		/* Q49 dp playlist ,first approach same as LIS , we find max while
		applying LIS here we have to make sure 2 billboards are placed at a
		greater distance of x , which becomes the constraint between i and j
		*/
			int ans = Integer.MIN_VALUE;
			int dp[] = new int[revenue.length];
			dp[0]=revenue[0];
			
			for(int i = 1 ; i < dp.length ;i++){
				
				int profit = revenue[i];
				for(int j = i-1 ; j >=0 ; j--){
					int potential = dp[j] + revenue[i];

					if(billboards[i] - billboards[j] > x)
					profit = Math.max(potential , profit);
				}
				dp[i] = profit;

				ans = Math.max(ans , dp[i]);
			}
			return ans;
		
	}

}
content_copyCOPY

https://www.codingninjas.com/codestudio/problems/highway-billboards_3125967