Given an array, its ith element is the price of a given stock on the ith day. If you only allow one trade (buy and sell a stock once), design an algorithm to calculate the maximum profit you can make. Note: You cannot sell a stock before you buy it.

Example 1:

Input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6), maximum profit = 6-1 = 5. Note that the profit cannot be 7-1 = 6, because the selling price needs to be higher than the buying price; Also, you can’t sell stocks before you buy them. Example 2:

Input: [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0. 121: The best time to buy and sell stocks

The first idea is to use a double for loop and then time out.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size(a);int ans=0;
        for(int i=0; i<n; i++) {for(int j=0; j<i; j++) { ans =max(ans,prices[i]-prices[j]); }}if(ans<=0)ans=0;
        returnans; }};Copy the code

Second idea: dp[I] : represents the maximum value that can be obtained in the previous day. Dp [I] can be obtained in two ways: 1. Calculate the minimum purchase price of i-1 day before and the selling price of i-1 day before; 2. If the input is empty, return 0(boundary case). If you create a new dp array, you don’t need to use ans, because we only use two states of the DP array.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size(a);if(n==0) return 0;
        int ans=0;
        int minnum =prices[0];
        for(int i=1; i<n; i++) { minnum=min(minnum,prices[i]);
            ans=max(ans,prices[i]-minnum);
        }
        if(ans<=0)ans=0;
        returnans; }};Copy the code