This is the second day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 35th day 🎈!
🚀 Algorithm 🚀

🌲 The best time to buy and sell stocks

Given an array prices, its ith element prices[I] represents the price of a given stock on day I.

You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.

Return the maximum profit you can make from the transaction. If you can’t make any profit, return 0.

Example 1:

Input:7.1.5.3.6.4] output:5Explanation: In no2Day (stock price =1) time to buy, at No5Day (stock price =6), maximum profit =6- 1 = 5. Notice the profit can't be7- 1 = 6Because the selling price needs to be higher than the buying price; Also, you can't sell stocks before you buy them.Copy the code

Example 2:

Enter: prices = [7.6.4.3.1] output:0Explanation: In this case, no transaction is completed, so the maximum profit is0.Copy the code

Tip:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

🌻C# method: dynamic programming

Thinking analytical

Using dynamic programming

Based on the graphic example given in the title, we need to define a Jagged array with the same length as numRows.

By observing the legend, it is not difficult to see that for two dimensional access variables like I and j, when j=0 or j= I, the target value is 1. Otherwise, the target value is dp[I][j] = dp[i-1][J-1] + DP [i-1][j].

Code:

public class Solution {
    public IList<IList<int>> Generate(int numRows) {
        int[][] dp =new int[numRows][];
        for(int i = 0; i<numRows; i++) { dp[i] =new int[i+1];
            for(int j = 0; j<=i; j++) {if(j==0 || j ==i)
                {
                    dp[i][j] = 1;
                }
                else
                {
                    dp[i][j] = dp[i- 1][j- 1] + dp[i- 1][j];
                }
            }
        }

        IList<IList<int>> p = new List<IList<int> > ();for(int i = 1; i<= numRows; i++) {var list = dp[i- 1].ToList();
            p.Add(list);
        }
        
        returnp; }}Copy the code

The execution result

By execution time:212Ms, in all CBeat 31.47% of users in # commitMemory consumption:25.9MB, in all CBeat 52.99% of users in # commit
Copy the code

🌻Java method 1: Brute force method

Thinking analytical

We need to find the maximum difference (i.e., maximum profit) between two numbers in a given array. In addition, the second number (selling price) must be greater than the first number (buying price).

Formally, for each set of I and j (where j > I) we need to find Max (prices[j]−prices[I]).

Code:

public class Solution {
    public int maxProfit(int prices[]) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if(profit > maxprofit) { maxprofit = profit; }}}returnmaxprofit; }}Copy the code

The execution result

By execution time:0Ms, beat out all Java commits100.00% user memory consumption:36.3MB, beat out all Java commits38.54% of the userCopy the code

Complexity analysis

Time complexity: O(n^2) where n is the length of the array. Each number is accessed only once. Space complexity: O(1) where n is the length of the array. The spatial complexity does not consider the return value, so the spatial complexity depends primarily on the depth of the recursive stack, which is O(logn).Copy the code

🌻Java Method 2: Iterate once

Thinking analytical

Code:

public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if(prices[i] - minprice > maxprofit) { maxprofit = prices[i] - minprice; }}returnmaxprofit; }}Copy the code

The execution result

By execution time:2Ms, beat out all Java commits94.82% user memory consumption:51.3MB, beat out all Java commits66.02% of the userCopy the code

Complexity analysis

Time: O(n) Space: O(1 )
Copy the code

💬 summary

  • Today is the thirty-fifth day of clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!