Maximize the Profit by Selling at-most M Products in Java

The problem is to maximize profit by selling at most M products. You are given an array of prices, where each element represents the price of a product. The goal is to select at most M products from the array in such a way that the total profit obtained from selling these products is maximized.

Example

Input

costPrice = { 2, 3, 1, 5, 4, 2 };

sellingPrice = { 6, 8, 5, 10, 9, 7 };

Output

20

Explanation: Here we have two lists that contain cost prices CP[] and selling prices SP[] of products respectively. The task is to maximize the profit by selling at-most ‘M’ products it can be solved using a greedy algorithm and dynamic programming.

Approach: Greedy Algorithm

Example 1

In the above code, we have to sell the fruits at max price. The program takes the cost prices of fruits (costPrice) and their respective selling prices (sellingPrice) as inputs. In the main method, we set the values of N and M to 6 and 4, respectively. The costPrice and sellingPrice arrays are initialized with the corresponding values for each fruit. Finally, the maximizeProfit method is called with the provided inputs, and the result, which is the maximum profit, is printed.

FileName: FruitPro.java

import java.util.*;
class FruitPro {
 // Function to find profit
 static int maximizeProfit(int N, int M, int[] costPrice, int[] sellingPrice) {
 Integer[] profit = new Integer[N];
 // Calculating profit for each fruit
 for (int i = 0; i < N; i++)
 profit[i] = sellingPrice[i] - costPrice[i];
 // Sort the profit array in descending order
 Arrays.sort(profit, Collections.reverseOrder());
 // Variable to calculate total profit
 int totalProfit = 0;
 // Check for the best M profits
 for (int i = 0; i < M; i++) {
 if (profit[i] > 0)
 totalProfit += profit[i];
 else
 break;
 }
 return totalProfit;
 }
 // Driver Code
 public static void main(String args[]) {
 int N = 6, M = 4;
 int[] costPrice = { 2, 3, 1, 5, 4, 2 };
 int[] sellingPrice = { 6, 8, 5, 10, 9, 7 };
 int maxProfit = maximizeProfit(N, M, costPrice, sellingPrice);
 System.out.println("Maximum Profit: $" + maxProfit);
 }
}

Output

Maximum Profit: $20

Complexity

The given code has a time complexity of O(N log N) and a space complexity of O(N).

The time complexity of O(N log N) arises from the sorting operation performed on the profit array using Arrays.sort(). As the number of fruits, N, increases, the time required to sort the array grows in a logarithmic manner.

The space complexity of O(N) is due to the additional array used to store the calculated profits. It grows linearly with the number of fruits, N. The rest of the variables and operations in the code have constant space requirements and do not contribute significantly to the overall space complexity.

In summary, the code has a time complexity of O(N log N) and a space complexity of O(N), with N representing the number of fruits.

Approach: Dynamic Programming

Example 2

In the above code, we have two arrays: costPrices and sellingPrices. The costPrices array contains the cost price of each product, and the sellingPrices array contains the corresponding selling price of each product.In the main method, we have added sample arrays for costPrices and sellingPrices, and set M to 3. The code calculates the maximum profit by considering the cost and selling prices using the maximizeProfit function, and then prints the result.

FileName: MaximizeProfit.java

public class MaximizeProfit {
 public static int maximizeProfit(int[] costPrices, int[] sellingPrices, int M) {
 int n = costPrices.length;
 int[][] dp = new int[n + 1][M + 1];
 // Fill the dynamic programming table
 for (int i = 1; i <= n; i++) {
 for (int j = 1; j <= M; j++) {
 if (j >= i) {
 // If the number of products to select is greater than or equal to the current product index,
 // we can choose to include the current product or exclude it
 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - i] + (sellingPrices[i - 1] - costPrices[i - 1]));
 } else {
 // If the number of products to select is less than the current product index,
 // we cannot include the current product
 dp[i][j] = dp[i - 1][j];
 }
 }
 }
 return dp[n][M];
 }
 public static void main(String[] args) {
 int[] costPrices = {8, 20, 15, 40, 30};
 int[] sellingPrices = {10, 30, 25, 50, 40};
 int M = 3;
 int maxProfit = maximizeProfit(costPrices, sellingPrices, M);
 System.out.println("Maximum Profit: " + maxProfit);
 }
}

Output

Maximum Profit: 12

Complexity

The time complexity of the code is O(n * M), and the space complexity is O(n * M), where n is the number of products and M is the maximum number of products to select. Both complexities are directly proportional to the product of n and M.