Advanced Java Programs: Dynamic & Greedy
10. Longest Increasing Subsequence - Dynamic Programming
Find the length of the longest increasing subsequence in an array.
import java.util.*;
public class LongestIncreasingSubsequence {
public static int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int max = 0;
for (int len : dp) {
max = Math.max(max, len);
}
return max;
}
public static void main(String[] args) {
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println("Length of LIS: " + lengthOfLIS(nums));
}
}
11. Matrix Chain Multiplication - Dynamic Programming
Given the dimensions of matrices, find the minimum number of multiplications needed to multiply the
chain.
public class MatrixChainMultiplication {
public static int matrixChainOrder(int[] p) {
int n = p.length;
int[][] dp = new int[n][n];
for (int len = 2; len < n; len++) {
for (int i = 1; i < n - len + 1; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int q = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
if (q < dp[i][j]) dp[i][j] = q;
}
}
}
return dp[1][n - 1];
}
public static void main(String[] args) {
int[] dimensions = {40, 20, 30, 10, 30};
System.out.println("Minimum multiplications: " + matrixChainOrder(dimensions));
}
}
12. Job Sequencing Problem - Greedy
Given jobs with deadlines and profits, schedule jobs to maximize profit if only one job can be done
at a time.
import java.util.*;
class Job {
char id;
int deadline, profit;
Job(char id, int deadline, int profit) {
this.id = id;
this.deadline = deadline;
this.profit = profit;
}
}
public class JobSequencing {
public static int maxProfit(Job[] jobs) {
Arrays.sort(jobs, (a, b) -> b.profit - a.profit);
int maxDeadline = 0;
for (Job job : jobs) maxDeadline = Math.max(maxDeadline, job.deadline);
boolean[] slots = new boolean[maxDeadline];
int totalProfit = 0;
for (Job job : jobs) {
for (int j = job.deadline - 1; j >= 0; j--) {
if (!slots[j]) {
slots[j] = true;
totalProfit += job.profit;
break;
}
}
}
return totalProfit;
}
public static void main(String[] args) {
Job[] jobs = {
new Job('a', 2, 100),
new Job('b', 1, 19),
new Job('c', 2, 27),
new Job('d', 1, 25),
new Job('e', 3, 15)
};
System.out.println("Max profit: " + maxProfit(jobs));
}
}
13. Minimum Number of Platforms - Greedy
Given arrival and departure times of trains, find the minimum number of platforms required at the
station.
import java.util.*;
public class MinPlatforms {
public static int findPlatform(int[] arr, int[] dep, int n) {
Arrays.sort(arr);
Arrays.sort(dep);
int platforms = 1, result = 1;
int i = 1, j = 0;
while (i < n && j < n) {
if (arr[i] <= dep[j]) {
platforms++;
i++;
} else {
platforms--;
j++;
}
result = Math.max(result, platforms);
}
return result;
}
public static void main(String[] args) {
int[] arr = {900, 940, 950, 1100, 1500, 1800};
int[] dep = {910, 1200, 1120, 1130, 1900, 2000};
int n = arr.length;
System.out.println("Minimum platforms needed: " + findPlatform(arr, dep, n));
}
}
