LeetCode 2898: Maximum Linear Stock Score

Explanation:

To solve this problem, we can use dynamic programming with two states: the current day we are at, and whether we currently hold a stock or not. We'll keep track of the maximum possible score we can achieve at each state.

At each day, we can either:

1. Buy a stock if we don't hold one already.
2. Sell the stock if we hold one.
3. Skip the day and do nothing.

The key idea is to transition between these states based on the actions that maximize the score.

Here are the steps for the algorithm:

1. Initialize two arrays hold and notHold each with a size of the number of days, where hold[i] represents the maximum score we can achieve on day i if we hold a stock, and notHold[i] represents the maximum score on day i if we don't hold a stock.
2. Iterate through each day starting from the first day:
   • If we are holding a stock on day i, we can either continue holding it (do nothing) or sell it. We choose the action that results in a higher score.
   • If we are not holding a stock on day i, we can either buy a stock or do nothing. We choose the action that results in a higher score.
3. The answer will be the maximum score between holding a stock on the last day or not holding a stock on the last day.

The time complexity of this algorithm is O(n) where n is the number of days, and the space complexity is also O(n) since we are using two arrays of size n to store the maximum scores.

:

class Solution {
    public int maxLinearStockScore(int[] prices) {
        int n = prices.length;
        int[] hold = new int[n];
        int[] notHold = new int[n];
        
        hold[0] = -prices[0];
        
        for (int i = 1; i < n; i++) {
            hold[i] = Math.max(hold[i - 1], notHold[i - 1] - prices[i]);
            notHold[i] = Math.max(notHold[i - 1], hold[i - 1] + prices[i]);
        }
        
        return Math.max(hold[n - 1], notHold[n - 1]);
    }
}