最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

算法计算出股票交易时间点,让你多赚一点

XAMPP案例 admin 285浏览 0评论

第一题

题目描述:

给定一段时间内每天的股票价格,已知你只可以买卖各一次,求最大的收益。

输入输出样例:
输入一个一维整数数组,表示每天的股票价格;输出一个整数,表示最大的收益。

Input:[7,1,5,3,6,4]
Output:5

在这个样例中,最大的利润为在第二天价格为 1 时买入,在第五天价格为 6 时卖出。

 

题解: 
我们可以遍历一遍数组,在每一个位置 i 时,记录 i 位置之前所有价格中的最低价格,然后 将当前的价格作为售出价格,查看当前收益是不是最大收益即可。

int maxProfit(vector<int>& prices) {
    int sell = 0, buy = INT_MIN;
    for (int i = 0; i < prices.size(); ++i) {
       buy = max(buy, -prices[i]);
       sell = max(sell, buy + prices[i]);
    }
    return sell;
}

第二题

题目描述:
给定一段时间内每天的股票价格,已知你只可以买卖各 k 次,且每次只能拥有一支股票,求 最大的收益。

 

输入输出样例:
输入一个一维整数数组,表示每天的股票价格;以及一个整数,表示可以买卖的次数 k。输 出一个整数,表示最大的收益。

Input: [3,2,6,5,0,3], k = 2
Output:7

在这个样例中,最大的利润为在第二天价格为 2 时买入,在第三天价格为 6 时卖出;再在第 五天价格为 0 时买入,在第六天价格为 3 时卖出。

 

题解: 
如果 k 大约总天数,那么我们一旦发现可以赚钱就进行买卖。如果 k 小于总天数,我们可以 建立两个动态规划数组 buy 和 sell,对于每天的股票价格,buy[j] 表示在第 j 次买入时的最大收 益,sell[j] 表示在第 j 次卖出时的最大收益。

// 主函数

int maxProfit(int k, vector<int>& prices) {
    int days = prices.size();
    if (days < 2) {
        return 0;
    }
    if (k >= days) {
        return maxProfitUnlimited(prices);
    }
    vector<int> buy(k + 1, INT_MIN), sell(k + 1, 0);
    for (int i = 0; i < days; ++i) {
        for (int j = 1; j <= k; ++j) {
            buy[j] = max(buy[j], sell[j-1] - prices[i]);
            sell[j] = max(sell[j], buy[j] + prices[i]);
        } }
    return sell[k];
}
// 辅函数
int maxProfitUnlimited(vector<int> prices) {
    int maxProfit = 0;
    for (int i = 1; i < prices.size(); ++i) {
       if (prices[i] > prices[i-1]) {
           maxProfit += prices[i] - prices[i-1];
} }
    return maxProfit;
}

Swift 编程语言版本

func maxProfit(_ prices: [Int]) -> Int {
    calculateProfit(prices, 0)
}

func calculateProfit(_ prices: [Int], _ index: Int) -> Int {
    if index >= prices.count {return 0}
    var max = 0
    for i in 0..<prices.count {
        var maxProfit = 0
        for j in i+1..<prices.count {
            if prices[i] < prices[j] {
                let curProfit = prices[j] - prices[i] + calculateProfit(prices, i + 1)
                if curProfit > maxProfit {
                    maxProfit = curProfit
                }
            }
        }
        if maxProfit > max {
            max = maxProfit
        }
    }
    return max
}
end

转载请注明:XAMPP中文组官网 » 算法计算出股票交易时间点,让你多赚一点

您必须 登录 才能发表评论!