买卖股票的最佳时机 II
给定一个数组，它的第i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入:[7,1,5,3,6,4]输出:7解释:在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入:[1,2,3,4,5]输出:4解释:在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入:[7,6,4,3,1]输出:0解释:在这种情况下, 没有交易完成, 所以最大利润为 0。
这道题没什么太多说的,就是贪心算法 贴个贪心算法的定义
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
刚好在做递归的题,写一点点感想:计算机里的很多问题都很庞大,但他们又存在一些相关的地方,比如二叉树之类的,这个时候有可能只需要考虑一步问题或者一小块问题,然后让它自己照着思路去循环就可以了,我们考虑只需要考虑一下结果判定 还有一些特殊情况即可.
代码:
public class Solution
{
public int MaxProfit(int[] prices)
{
int p = 0;
int a = 0;
for (int i = 1; i < prices.Length; i++)
{
p = prices[i] - prices[i - 1];
if (p > 0) a += p;
}
return a;
}
}
没啥好讲的 看不懂就多看看...
网友评论