Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
|
1 2 3 4 |
Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price) |
Example 2:
|
1 2 3 4 |
Input: [7, 6, 4, 3, 1] Output: 0 In this case, no transaction is done, i.e. max profit = 0. |
题目链接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
一堆股票价格 – 每天买一次卖一次 – 问最大收益 Eazy难度 – 不过2016携程笔试考到了原题，所以就翻出来Ac了一下…
提交代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public: int maxProfit(vector<int>& prices) { int num = prices.size(); if(num <= 0)return 0; int min = prices[0]; int max = 0; for(int i=1; i<num; i++) { if(prices[i] > min && prices[i] - min > max) { max = prices[i] - min; } else if(prices[i] < min) { min = prices[i]; } } return max; } }; |
携程AC代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> #include <vector> using namespace std; vector <int> v; vector <int> value; int main() { // freopen("input.txt", "r", stdin); int a; while(cin >> a) { getchar(); v.push_back(a); value.push_back(0); } //for(int i=0; i<v.size(); i++) //{ // cout << v[i] << " "; //} //cout << endl; int num = v.size(); int min = v[0]; int max = 0; for(int i=1; i<num; i++) { if(v[i] > min && v[i] - min > max) { max = v[i] - min; } else if(v[i] < min) { min = v[i]; } } cout << max << endl; } |
嗯 – 就是酱…
【LeetCode】121. Best Time to Buy and Sell Stock