Dynamic Programming 03

Given an integer N denoting the Length of a line segment. You need to cut the line segment in such a way that the cut length of a line segment each time is either x, y, or z. Here x, y, and z are integers.
After performing all the cut operations, your total number of cut segments must be maximum.

Problem link :- click here

Code

import java.util.Scanner;

//	MAXIMIZE THE CUT SEGMENT

public class DynamicProgramming_03
{
	
	//	Recursion and Memoization(its not spelling mistake)
	static int maxCut(int l, int p, int q, int r, int arr[])
	{
		int min = Math.min(   Math.min(p, q), r   );
		int option_p = 0;
		int option_q = 0;
		int option_r = 0;
		
		if( l < min  ||  l == 0 )
			return 0;
		if(arr[l] != 0)
			return arr[l];
		if(p <= l)
			option_p = maxCut(l-p, p, q, r, arr);
		if(q <= l)
			option_q = maxCut(l-q, p, q, r, arr);
		if(r <= l)
			option_r = maxCut(l-r, p, q, r, arr);
		
		int ans = Math.max(   Math.max(option_p, option_q), option_r   ) + 1;
		
		arr[l] = ans;
		return ans;
	}
	
	// Dynamic Programming
	static int maxCut2(int l, int p, int q, int r)
	{
		int arr[] = new int[l+1];
		
		for(int i=0; i<=l; i++)
			arr[i] = -1;
		
		arr[0] = 0;
		
		for(int i=0; i<=l; i++)
		{
			if(arr[i] == -1)
				continue;
			
			if( i+p <= l)
				arr[i+p] = Math.max(arr[i+p], arr[i] + 1);
			if( i+q <= l)
				arr[i+q] = Math.max(arr[i+q], arr[i] + 1);
			if( i+r <= l)
				arr[i+r] = Math.max(arr[i+r], arr[i] + 1);
		}
		
		if(arr[l] == -1)
			arr[l] = 0;
		
		return arr[l];
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		System.out.print("Enter the line length : ");
		int l = s.nextInt();
		
		System.out.println("Enter the three line segment values : ");
		int p = s.nextInt();
		int q = s.nextInt();
		int r = s.nextInt();
		
		int arr[] = new int[l+1];
		System.out.println("Maximum cut = " + maxCut2(l, p, q, r));
		
		s.close();
	}

}