Permutations of given array:
Subsets of given array:
public class Runner {
public static void main(String[] args) {
int a[]={1,2,3};
permutation(a,0);
}
private static void permutation(int[] a,int k) {
if(k==a.length-1){
System.out.println(Arrays.toString(a));
return;
}
for (int i = k; i <a.length; i++) {
int temp=a[k];
a[k]=a[i];
a[i]=temp;
permutation(a,k+1);
temp=a[k];
a[k]=a[i];
a[i]=temp;
}
}
}Subsets of given array:
public static void printSubSets(int arr[],int last,int k[]){
if(last==arr.length){
System.out.println(Arrays.toString(k));
return;
}int x = arr[last];
k[last] = x;
printSubSets(arr, last + 1, k);
k[last] = -1;
printSubSets(arr, last + 1, k);
}
public static void main(String[] args) {
int arr[]={1,2,3};
int k[]={-1,-1,-1};
printSubSets(arr,0,k);
}
Forwarded from Learn Java
problem is to find a path from the upper-left corner to the lower-right corner
of an n × n grid, with the restriction that we may only move down and right. Each
square contains an integer, and the path should be constructed so that the sum of the
values along the path is as large as possible.
divide and conquer approach:
of an n × n grid, with the restriction that we may only move down and right. Each
square contains an integer, and the path should be constructed so that the sum of the
values along the path is as large as possible.
divide and conquer approach:
public static int maxPath(int value[][],int x,int y){dynamic programming approach:
if(x==0 || y==0){
return value[x][y];
}
int max= Integer.MIN_VALUE;
max = Math.max(maxPath(value,x-1,y),maxPath(value,x,y-1))+value[x][y];
return max;
}
public static int maxPath(int value[][],int x,int y,int memory[][]){Driver code:
if(x==0 || y==0){
return value[x][y];
}
if(memory[x][y]!=Integer.MIN_VALUE){
return memory[x][y];
}
int max= Integer.MIN_VALUE;
max = Math.max(maxPath(value,x-1,y),maxPath(value,x,y-1))+value[x][y];
memory[x][y]=max;
return max;
}
public static void main(String[] args) {
int value[][]= {
{3,7,9,2,7},
{9,8,3,5,5},
{1,7,9,8,5},
{3,8,6,4,10},
{6,3,9,7,8}
};
int mem[][]= new int[5][5];
for(int i=0;i<mem.length;i++) {
Arrays.fill(mem[i],Integer.MIN_VALUE);
}
System.out.println(maxPath(value,4,4,mem));
}
👍6
Largest Sum Contiguous Subarray Dynamic programming approach :
public class KadaneAlgorithm {
public static int findMaxSubArray(int[] nums) {
int maxSoFar = nums[0];
int maxEndingHere = nums[0];
for (int i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
public static void main(String[] args) {
int[] nums = { -2, -3, 4, -1, -2, 1, 5, -3 };
int maxSum = findMaxSubArray(nums);
System.out.println("حداکثر مجموع زیرآرایه: " + maxSum);
}
}
👍4
Suppose that we are given a set of coin values coins = {c1, c2,..., ck } and a
target sum of money n, and we are asked to construct the sum n using as few coins as
possible. There are no restrictions on how many times we can use each coin value.
Divide and conquer approach:
target sum of money n, and we are asked to construct the sum n using as few coins as
possible. There are no restrictions on how many times we can use each coin value.
Divide and conquer approach:
public static int maxCoin(int n,int []price){Dynamic programming approach:
if(n==0){
return 0;
}
int q = Integer.MAX_VALUE;
for(int i=0;i<price.length;i++){
if(n- price[i]>=0) {
q = Math.min(maxCoin(n - price[i], price) + 1, q);
}
}
return q;
}
public static int dpMaxCoin(int n,int []price,int res[]){Driver code:
if(n==0){
return 0;
}
if(res[n]>-1){
return res[n];
}else {
int q = Integer.MAX_VALUE;
for (int i = 0; i < price.length; i++) {
if (n - price[i] >= 0) {
q = Math.min(dpMaxCoin(n - price[i], price,res) + 1, q);
}
}
res[n]=q;
}
return res[n];
}
public static void main(String[] args) {
int [] arr = {1,3,4};
int res[] = new int[15];
Arrays.fill(res,-1);
System.out.println(maxCoin(14,arr));
System.out.println(dpMaxCoin(14,arr,res));
}
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class DFS {
private static boolean[] visited = new boolean[6];
private static List<List<Integer>> adj = new ArrayList<>(10);
public static void main(String[] args) {
adj.add(List.of(0));
adj.add(1, List.of(2, 4));
adj.add(2, List.of(3, 1, 5));
adj.add(3, List.of(2, 5));
adj.add(4, List.of(1));
adj.add(5, List.of(3, 2));
dfs(1);
}
//O(n+m)
public static void dfs(int s) {
List<Integer> adjOfNodeS = adj.get(s);
if (visited[s]) return;
visited[s] = true;
System.out.println("Visit :" + s);
for (int i : adjOfNodeS) {
dfs(i);
}
}
}
output :
Visit :1
Visit :2
Visit :3
Visit :5
Visit :4
import java.util.LinkedList;
import java.util.List;
public class DFS {
private static boolean[] visited = new boolean[6];
private static List<List<Integer>> adj = new ArrayList<>(10);
public static void main(String[] args) {
adj.add(List.of(0));
adj.add(1, List.of(2, 4));
adj.add(2, List.of(3, 1, 5));
adj.add(3, List.of(2, 5));
adj.add(4, List.of(1));
adj.add(5, List.of(3, 2));
dfs(1);
}
//O(n+m)
public static void dfs(int s) {
List<Integer> adjOfNodeS = adj.get(s);
if (visited[s]) return;
visited[s] = true;
System.out.println("Visit :" + s);
for (int i : adjOfNodeS) {
dfs(i);
}
}
}
output :
Visit :1
Visit :2
Visit :3
Visit :5
Visit :4
👍7
import java.lang.System.Logger;
import java.lang.System.Logger.Level;
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class ConnectToDatabase {
private final static Logger LOGGER = System.getLogger(ConnectToDatabase.class.getName());
private static final String URL_CONNECTION = "jdbc:mysql://localhost:3306/DBNAME";
private static final String USERNAME = "";
private static final String PASSWORD = "";
private ConnectToDatabase() {
}
public static CompletableFuture<Connection> connectToDatabase() {
CompletableFuture<Connection> connectionFuture = new CompletableFuture<>();
final ExecutorService executorService = Executors.newSingleThreadExecutor();
executorService.execute(() -> {
try {
final Connection connection = DriverManager.getConnection(URL_CONNECTION, USERNAME, PASSWORD);
LOGGER.log(Level.INFO, "Successfully connection database");
connectionFuture.complete(connection);
} catch (SQLException e) {
LOGGER.log(Level.ERROR, "Fail to connecting to database", e);
connectionFuture.completeExceptionally(e);
} finally {
executorService.shutdown();
LOGGER.log(Level.INFO, "Successfully shutdown executor");
}
});
return connectionFuture;
}
}
👍7
Maximum sum submatrix:
O(n^6)
O(n^6)
public static void main(String[] args) {
int num[][]= {{-111,-18,-66},{-852,-112,12},{-132,-179,699}};
int max = Integer.MIN_VALUE;
for (int i = 0; i < num.length; i++) {
for (int j = i; j < num.length; j++) {
for (int k = 0; k <num[0].length ; k++) {
for (int l = k; l < num[0].length; l++) {
int nu=0;
for (int m = i; m <= j; m++) {
for (int n = k; n <=l ; n++) {
nu+=num[m][n];
}
}
if(nu>max){
max=nu;
}
}
}
}
}
System.out.println(max);
}👍5
Longest common subsequence(Dynamic programming):
Driver code:
public static int LCS(char[] a, int ai, int bi, char[] b, int match, int r[][]) {
if (ai == -1 || bi == -1) {
return 0;
}
if (r[ai][bi] > -1) {
return r[ai][bi];
}
if (a[ai] == b[bi]) {
int q = LCS(a, ai - 1, bi - 1, b, match + 1, r);
r[ai][bi] = q + 1;
return r[ai][bi];
}
int p2 = LCS(a, ai, bi - 1, b, match, r);
int p3 = LCS(a, ai - 1, bi, b, match, r);
int max = Math.max(p3, p2);
r[ai][bi] = Math.max(r[ai][bi], max);
return max;
}Driver code:
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String a= scanner.nextLine();
String b=scanner.nextLine();
int r[][] = new int[a.length()][b.length()];
for (int i = 0; i < r.length; i++) {
for (int j = 0; j < r[i].length; j++) {
r[i][j]=-1;
}
}
System.out.println(LCS(a.toCharArray(),a.length()-1,b.length()-1,b.toCharArray(),0,r));
}👍6
Longest Increasing subsequence(LIS):
Dynamic programming bottom up approach
Dynamic programming bottom up approach
import java.util.Arrays;
public class LongestIncreasingSubsequence {
public static void main(String[] args) {
int a[] = {3, 10, 2, 1, 20};
int length[] = new int[a.length];
Arrays.fill(length,1);
for (int i = 1; i < a.length; i++) {
int q= 1;
for (int j = 0; j <= i; j++) {
if (a[i]>a[j]){
if(q<=length[j]) {
q = length[j] + 1;
}
}
}
length[i]=q;
}
System.out.println(max(length));
}
public static int max(int a[]){
int max=-1;
for (int i = 0; i < a.length; i++) {
if(max<a[i]){
max=a[i];
}
}
return max;
}
}