Scribd
Upload
1 views

Advanced_Java_Dynamic_Greedy_Problems

The document presents advanced Java programs focusing on dynamic programming and greedy algorithms. It includes implementations for the Longest Increasing Subsequence, Matrix Chain Multiplication, Job Sequencing Problem, and Minimum Number of Platforms. Each section provides code examples and explanations for solving specific algorithmic problems.

Uploaded by

bhavanipriy73
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
1 views

Advanced_Java_Dynamic_Greedy_Problems

The document presents advanced Java programs focusing on dynamic programming and greedy algorithms. It includes implementations for the Longest Increasing Subsequence, Matrix Chain Multiplication, Job Sequencing Problem, and Minimum Number of Platforms. Each section provides code examples and explanations for solving specific algorithmic problems.

Uploaded by

bhavanipriy73
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

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));
}
}

You might also like