AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

股票买入问题 -- 练习暴力求解(笔记)

作者: 作者的头像   Tie ,  2019-09-08 12:35:04 ,  所有人可见 ,  阅读 1048


2


1

枚举:股票问题

思路:枚举什么时候卖出

  • 练习如何更新数值
  • 如何暴力求解

题目1

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖 一次 该股票可能获得的利润是多少?
例如一只股票在某些时间节点的价格为[9, 11, 8, 5, 7, 12, 16, 14]。
如果我们能在价格为5的时候买入并在价格为16时卖出,则能收获最大的利润11

//O(n)
class Solution {
public:
    int maxDiff(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        if (nums.empty()) return 0;
        for (int i = 1, minv = nums[0]; i < n; i ++ )
        {
            res = max(res, nums[i] - minv);
            minv = min(minv, nums[i]);
        }
        return res;
    }
};
//O(n^2)
class Solution {
public:
    int maxDiff(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        if (nums.empty()) return 0;
        for (int i = 1; i < n; i ++ )
            for(int j = 1; j < i; j ++)
            {
                int minv = nums[0];
                if (minv > nums[j]) minv = nums[j];
                res = max(res, nums[i] - minv);
            }
        return res;
    }
};

题目2
* Design an algorithm to find the maximum profit. You may complete at most two transactions

  • 解法一
class Solution {
public:
    int maxDiff(vector<int>& nums) {
        int n = nums.size();
        int profit1 = 0, profit2 = 0;
        int profit = 0;
        if (nums.empty()) return 0;
        //枚举什么时候第一次卖出
        for (int i = 1, minv1 = nums[0]; i < n; i ++ )
            //枚举第二次卖出的情况
            for(int j = i + 2, minv2 = nums[i + 1]; j < n; j ++)
            {
                if(minv1 > nums[i]) minv1 = nums[i]; //更新前i-1个数中的最小值i
                if(minv2 > nums[j]) minv2 = nums[j]; //更新前i+1到n个数中的最大值
                profit1 = nums[i] - minv1;
                profit2 = nums[j] - minv2;
                profit = max(profit, profit1 + profit2);
                //if (i == 5 && j == 6) cout << maxv << " " << profit2 << endl;
                //if (i == 5 && j == 7) cout << maxv << " " << profit2 <<  endl;
                cout << "第一次卖出: " << nums[i] << " " 
                << "minv1: " << minv1 << " " << "profit1: " << profit1 << endl;
                cout << "第二次卖出: " << nums[j] << " " 
                << "minv2: " << minv2 << " " << "profit2: " << profit2 << endl;
                cout << "profit: " << profit << endl; 
            }

        return profit;
    }
};
  • 解法二
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int minv = INT_MAX;
        int maxv = INT_MIN;
        int profit1 = 0, profit2;
        int total_profit;
        vector<int> f(n, 0); //f[i]表示第一次卖出时的最大利润
        // 特判:
        if (prices.empty()) return 0;
        //枚举第一次卖出时的情况(可能不是最后一个卖出)
        for (int i = 0; i < n; i ++ )
        {
            //最大利润 = 卖出时的价格 - 卖出前的最小价格
            if (prices[i] < minv) minv = prices[i];
            profit1 = max(profit1, prices[i] - minv);
            f[i] = profit1;
        }

        //枚举第二次买入的情况(当前买入)
        total_profit = f[n - 1];
        for (int i = n - 1; i > 0; i -- )
        {
            //最大利润 = 买入后的最大价格 - 买入时的价格
            if (prices[i] > maxv) maxv = prices[i];
            profit2 = maxv - prices[i];
            //总共最大利润 = 只操作一次的最大利润 + 操作两次的最大利润
            total_profit = max(total_profit, f[i - 1] + profit2);
        }

        return total_profit;
    }
};
// 为什么 total_profit = max(f[n - 1], f[i - 1] + profit2); 这样写不可以?

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息