天天看点
返回

力扣 121 买卖股票的最佳时间

用了一种暴力算法 过于暴力 超时了 试了官方的C++也超时了

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //找最大 最小值 最小值下标在最大值下标之前
        vector<int>::iterator it; 
         int max=prices[0];
            int min=prices[0];
            int min_x=0;
            int max_x=0;
            for(int i=1;i<prices.size();i++)//最小值
        {
            if(min>prices[i])
            {
                min=prices[i];
                min_x=i;
            }
        }
         for(int i=1;i<prices.size();i++)//最大值
        {
            if(max<prices[i])
            {
                max=prices[i];
                max_x=i;
            }
        }  
         while(max_x<min_x)   //最大值坐标小于最小值时，则再从最大值加一开始遍历再找最大值 也可直接剔除最大值 但可能出错
         {
       for(int i=max_x+1;i<prices.size();i++)
           {
               if(max<prices[i])
            {
                max=prices[i];
                max_x=i;
            }
           }
         }
        int result=prices[max_x]-prices[min_x];
      return result;
    }
};

在这种写法中之前用到向量删除元素 造成野指针

for(vector::iterator iter=veci.begin(); iter!=veci.end(); iter++)

{

if( *iter == 3)

veci.erase(iter);

}

错误写法

因为earase结束后，iter变成了野指针，iter++就产生了错误。

erase()返回值是一个迭代器，指向删除元素下一个元素;如果是删除某范围内的元素时：返回值也表示一个迭代器，指向最后一个删除元素的下一个元素;

for(vector::iterator iter=veci.begin(); iter!=veci.end(); )

{

if( *iter == 3)

iter = veci.erase(iter);

else

iter ++

}

或

prices.erase(remove(prices.begin(),prices.end(),max),prices.end());

但是还是会超时

2.这是一个最大连续子数组和：

解答区有很多很棒的答案 建议详细阅读

有牛顿莱布尼茨公式可知

力扣 121 买卖股票的最佳时间

区间和可以由区间差来求 那么区间差自然可以有区间和来求

在上面的公式中，我们把 F()表示的数组称为前缀和。

最大连续子数组和可以使用动态规划求解， dp[i]dp[i] 表示以i为结尾的最大连续子数组和，递推公式为：

dp[i] = max(0, dp[i-1])

F(x)实际上是f(x)的原函数。在本题中，F(b)和F(a)分别代表买入卖出点，我们要算二者的差，所以F(b) - F(a) = sum(f(a), …f(b))。 f(a), f(b)是F(x)的导函数。所以这里应该先对股票序列求导，即前后做差，然后计算其连续子数组最大和。

而不是直接计算其连续子数组最大和

关于对序列求导即前后做差：差分法，是一种微分方程数值方法，是通过有限差分来近似导数，从而寻求微分方程的近似解。差分法就是把微分用有限差分代替，把导数用有限差商代替，从而把基本方程和边界条件（一般均为微分方程）近似地改用差分方程（代数方程）来表示，把求解微分方程的问题改换成为求解代数方程的问题。

新的数组元素为相邻元素之差，a[i]-a[j]=a[i]-a[i-1]+a[i-1]-a[i-2]+…+a[j+1]-a[j]=dif[i]+dif[i-1]+…+dif[j+1]。两数之差a[i]-a[j]相当于求最大连续子数组和，该数组为dif数组。

代码：（差分法）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<=1) return 0;
        int p;
     vector<int> diff(prices.size()-1);//两数差数组 有可能为负数
     for(int i=0;i<prices.size()-1;i++)
     {
         diff[i]=prices[i+1]-prices[i];
     }
     vector<int> dp(diff.size());//最大连续差数组的和
     dp[0]=max(0,diff[0]);//与0比较 找正数
     p=dp[0];
     for(int i=1;i<dp.size();i++)
     {
         dp[i]=max(0,dp[i-1]+diff[i]);//转换方程
         p=max(p,dp[i]);
     }
     return p;
    }
};

还可将diff和dp数组优化掉

建议详细阅读以下几篇文章与解答

详见:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-dp-7-xing-ji/

还有一篇讲解股票买卖类型题的(强烈建议仔细阅读）：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/

状态转移方程：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])

max( 选择 rest , 选择 sell )

解释：今天未持有两种可能：

昨天就没持有则为dp[i-1][k][0]

昨天有今天卖了则为dp[i-1][k][1] (昨天持有)+prices[i] (今天卖了)

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

max( 选择 rest , 选择 buy )

解释：今天我持有着股票，有两种可能：

要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；

要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。今天买入要减去prices[i]

// k == 1 可将k省去
int maxProfit_k_1(int[] prices) {
    int n = prices.length;
    // base case: dp[-1][0] = 0, dp[-1][1] = -infinity
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {  //用变量代替数组则不需要考虑数组越界（i-1==-1)的问题 
        // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        // dp[i][1] = max(dp[i-1][1], -prices[i])
        dp_i_1 = Math.max(dp_i_1, -prices[i]);
    }
    return dp_i_0;
}

123 K=2

int n=prices.size();
      int dp_i_10=0;
      int dp_i_20=0;
      int dp_i_11=INT_MIN;
      int dp_i_21=INT_MIN;
      for(int i=0;i<n;i++)
      {
          dp_i_10=max(dp_i_10,dp_i_11+prices[i]);
          dp_i_11=max(dp_i_11,-prices[i]);//dp[i-1][k-1][0] k=1时 k-1=0则其为0
          dp_i_20=max(dp_i_20,dp_i_21+prices[i]);
          dp_i_21=max(dp_i_21,dp_i_10-prices[i]);
      }
      return dp_i_20;

K=正无穷，有冰冻期

int maxProfit(vector<int>& prices) {
       // dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
       // dp[i][1]=max(dp[i-1][1],dp[i-2][0]-prices[i]);
        int n=prices.size();
        int dp_i_0=0;//前一个状态
        int dp_i_1=INT_MIN;
        int dp_pre_0=0;//dp[i-2][0]  前前一个状态
        for(int i=0;i<n;i++)
        {
            int temp=dp_i_0;
            dp_i_0=max(dp_i_0,dp_i_1+prices[i]);
            dp_i_1=max(dp_i_1,dp_pre_0-prices[i]);
            dp_pre_0=temp;//状态同样需要递进 递增
        }
        return dp_i_0;
    }

k为任意值

int maxProfit(int k, vector<int>& prices) {    
    if(prices.size()<2||k<1) return 0;
    if(k>=prices.size()/2) //k超过n/2则没有约作用 k=正无穷
    {
       int dp_i_0=0; int dp_i_1=INT_MIN;
       for(int i=0;i<prices.size();i++)
       {
           int temp=dp_i_0;
           dp_i_0=max(dp_i_0,dp_i_1+prices[i]);
           dp_i_1=max(dp_i_1,temp-prices[i]);
       }
       return dp_i_0;
    }
   else{
int n=prices.size(); 
    int dp[n][k+1][2]={0}; //注意dp数组位置
      for(int i=0;i<n;i++)
    { 
       for(int j=k;j>0;j--)
       { 
           if(i-1==-1)
        {
            dp[i][j][0]=0;
            dp[i][j][1]=-prices[i];
            continue;
        }
              dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
              dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
       } 
    }   
       return dp[n-1][k][0]; 
   } 
   }

关于区间和的文章：

https://zhuanlan.zhihu.com/p/54337418

这个题解答区的第二解让我对数学与编程，算法结合有了初步认识 推荐仔细研究

力扣 简单 数据结构 c++ 动态规划
上一篇: [Topcoder16346]TwoPerLineCXXV.[Topcoder16346]TwoPerLine
下一篇: CF913E Logical ExpressionCXXII.CF913E Logical Expression

继续阅读