Stock Trading Profit Maximization Problem

You are given an array representing the daily price of a stock. Your task is to write a Java algorithm to determine the best day to buy and the best day to sell the stock to maximize your profit. You are only permitted to complete a single transaction (i.e., buy one and sell one share of the stock), and you must sell the stock after you buy it.

Input: An array of integers where each integer represents the stock price on a given day. For example, consider the following array of stock prices:

int[] prices = {3, 5, 6, 1, 7, 2, 10, 9, 3};

Output: Your algorithm should return the best day to buy and the best day to sell to maximize profit. The days should be zero-indexed, where day 0 is the first day. If no profit can be made, return an appropriate message or values indicating such.

Example:

Given the input array [3, 5, 6, 1, 7, 2, 10, 9, 3], your algorithm should return:

Buy on day 3, sell on day 6

This is because buying the stock for 1 on day 3 and selling it for 10 on day 6 yields a maximum profit of 9.

Constraints:

- You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

- If you cannot achieve profit, return a statement such as "No profitable transaction is possible."

Requirements:

- Implement your solution in Java.

- Ensure your algorithm is efficient and handles all possible edge cases.

This question challenges you to think about efficient array traversal and finding the optimal pair of indices (days) to maximize the difference (profit) between them.

Solution: 

public class StockProfitCalculator {
    public static void main(String[] args) {
        int[] prices = {3, 5, 6, 1, 7, 2, 10, 9, 3};
        int[] result = maxProfitDays(prices);

        if (result[0] == -1) {
            System.out.println("No profitable transaction is possible.");
        } else {
            System.out.println("Buy on day " + result[0] + ", sell on day " + result[1]);
        }
    }

    public static int[] maxProfitDays(int[] prices) {
        int maxProfit = 0;
        int buyDay = 0;
        int sellDay = 0;
        boolean profitPossible = false;

        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxProfit) {
                    maxProfit = profit;
                    buyDay = i;
                    sellDay = j;
                    profitPossible = true;
                }
            }
        }

        if (profitPossible) {
            return new int[]{buyDay, sellDay};
        } else {
            return new int[]{-1, -1}; // Indicating no profitable transaction is possible
        }
    }
}

In this solution, the maxProfitDays method iterates over each day, considering it as a buying day, and then iterates over each subsequent day to consider it as a selling day. It calculates the profit for each pair of days and updates the maxProfit, buyDay, and sellDay if a higher profit is found. If a profitable transaction is possible, it returns an array containing the best days to buy and sell. Otherwise, it returns {-1, -1} indicating that no profitable transaction is possible. This brute force approach has a time complexity O(n²) of since it uses two nested loops to iterate through the array, where n is the length of the input array. While this solution works, it's not the most efficient for large arrays.

public class StockProfitCalculator {

    public static void main(String[] args) {
        int[] prices = {3, 5, 6, 1, 7, 2, 10, 9, 3};
        int[] result = findBestDaysToBuyAndSell(prices);
        
        if (result[0] == -1) {
            System.out.println("No profitable transaction is possible.");
        } else {
            System.out.println("Buy on day " + result[0] + ", sell on day " + result[1]);
        }
    }

    public static int[] findBestDaysToBuyAndSell(int[] prices) {
        if (prices == null || prices.length < 2) {
            return new int[]{-1, -1}; // Not enough days to make a transaction
        }
        
        int minPriceIndex = 0; // Index of minimum price so far
        int maxProfit = 0; // Maximum profit so far
        int buyDay = 0; // Day to buy to achieve maximum profit
        int sellDay = 0; // Day to sell to achieve maximum profit
        
        for (int i = 1; i < prices.length; i++) {
            // If we find a new minimum price, update minPriceIndex
            if (prices[i] < prices[minPriceIndex]) {
                minPriceIndex = i;
            }
            
            // Calculate profit if bought at min price so far and sold today
            int currentProfit = prices[i] - prices[minPriceIndex];
            
            // If current profit is greater than maxProfit, update maxProfit and days
            if (currentProfit > maxProfit) {
                maxProfit = currentProfit;
                buyDay = minPriceIndex;
                sellDay = i;
            }
        }
        
        // If maxProfit is 0, no profitable transaction is possible
        if (maxProfit == 0) {
            return new int[]{-1, -1};
        } else {
            return new int[]{buyDay, sellDay};
        }
    }
}

To solve this problem efficiently, we will use a single-pass approach. We need to maintain two variables: one for the minimum price seen so far and another for the maximum profit we can achieve. As we iterate through the array, we update these variables. This approach ensures a time complexity of O(n), where n is the number of days (array length).