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: Input: [7, 1, 5, 3, 6, 4] Output: 5
| // This is a supplement to the Active Template Library 3.0. | |
| // Copyright (C) 2000 Microsoft Corporation | |
| // All rights reserved. | |
| // | |
| // This source code is only intended for illustration. | |
| #ifndef __CPIMPLMT_H__ | |
| #define __CPIMPLMT_H__ | |
| #include <atlcom.h> |
| "Magic" Numbers | |
| Operation Time (us) Source | |
| L1 cache reference 0.0005 2,3 | |
| Execute typical instruction 0.0010 2,3 | |
| Branch mispredict 0.0050 2,3 | |
| Propagation delay in fiber-optic cable, per meter 0.0050 5 | |
| L2 cache reference 0.0070 2,3 | |
| Mutex lock/unlock (uncontested) 0.0250 2,3 | |
| Decode FAST message 0.0500 5 |