D
DevExCode

LeetCode 2898: Maximum Linear Stock Score Solution

Master LeetCode problem 2898 (Maximum Linear Stock Score), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2898. Maximum Linear Stock Score

Medium
ArrayHash Table

Problem Explanation

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.

:

Solution Code

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]);
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 2898 (Maximum Linear Stock Score)?

This page provides optimized solutions for LeetCode problem 2898 (Maximum Linear Stock Score) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2898 (Maximum Linear Stock Score)?

The time complexity for LeetCode 2898 (Maximum Linear Stock Score) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2898 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2898 in Java, C++, or Python.

Back to LeetCode Solutions