Algorithm：188. 买卖股票的最佳时机 IV；123. 买卖股票的最佳时机 III
Review： 应用函数编程原则
Tip/Tech：
Share：
Algorithm
123. 买卖股票的最佳时机 III
我把这里的状态的定义成五个状态，取每个状态的最大值，这里主要的状态有，买股票，卖股票，以及第一次，第二次交易的几个关键参数。
注意，这里的交易，要指的一买一卖才算一次交易。
int[][][] mp = new int[len][3][2];
// 没有交易，不买卖
mp[0][0][0] = 0;
// 没有交易，仅仅买入，就相当于亏了当天买入的价格
mp[0][0][1] = -prices[0];
// 第一次交易，卖出的状态
mp[0][1][0] = 0;
// 还没完成第二次的交易，仅仅是买入
mp[0][1][1] = Integer.MIN_VALUE;
// 第二次交易，要卖出操作的收益
mp[0][2][0] = 0;
根据以上的状态进行继续每天的状态的更新，因为股票，就是要低买，高卖才是挣钱，当然希望每次买入是最低价，我们可以看成每次买入都相当于当前的收益为负的价格，也就是我们是付出那么多钱的，那么你希望是一块买入还是十块买入呢？自然是一块钱的时候买入，也就是max(-1, -10)。卖出的思想也是一样。
public int maxProfit(int[] prices) {
int len = prices.length;if (len == 0) {
return 0;}int[][][] mp = new int[len][3][2];mp[0][0][0] = 0;mp[0][0][1] = -prices[0];mp[0][1][0] = 0;mp[0][1][1] = Integer.MIN_VALUE;mp[0][2][0] = 0;for (int i = 1; i < len; i ++) {
// 无股票状态 零次交易mp[i][0][0] = mp[i - 1][0][0];// 无股票开始第一次交易，在前一日和当天的值中取最大值mp[i][0][1] = Math.max(mp[i - 1][0][1], mp[i - 1][0][0] - prices[i]);// 第一次交易后 的无股票状态mp[i][1][0] = Math.max(mp[i - 1][1][0], mp[i - 1][0][1] + prices[i]);// 第一次交易后再次买入股票mp[i][1][1] = Math.max(mp[i - 1][1][1], mp[i - 1][1][0] - prices[i]);// 第一次交易后，再次卖出股票，完成两次交易mp[i][2][0] = Math.max(mp[i - 1][2][0], mp[i - 1][1][1] + prices[i]);}return Math.max(mp[len - 1][0][0], Math.max(mp[len - 1][1][0], mp[len - 1][2][0]));
}
当然，写到这里，肯定有人说，这样写是不节约空间的，网上有很多有用四个变量来进行记录状态的。其实最主要是为了下一题的讲解
188. 买卖股票的最佳时机 IV
我们先从上一题的思想入手，我们可以发现规律，其实k笔交易，就是每天记录每一笔交易的最优解，这样就可以用来进行推导了。核心代码就是下面这一段；
for (int i = 1; i < len; i ++) {
for (int j = 0; j <= k; ++j) {
if (j == 0) {
mp[j][0] = mp[0][0];} else {
mp[j][0] = Math.max(mp[j][0], mp[j - 1][1] + prices[i]);}mp[j][1] = Math.max(mp[j][1], mp[j][0] - prices[i]);}
}
即便是知道这个公式，基本就可以来求解了，但是你如果只用这些代码来提交，就会出现问题，最大的问题就是，当k非常大的时候，会内存不够用了，其实当k非常大的时候，是完全没有必要 ，因为，仔细思考就会发现，k的最有效的就是等于n的一半的时候。这样就已经接近了无数次的交易了。直接用贪婪的做法求解就行。
class Solution {
public int maxProfit(int k, int[] prices) {
int len = prices.length;int result = 0;if (len == 0 || k == 0) {
return 0;}if (k > len / 2) {
return greedy(prices);}int[][] mp = new int[k + 1][2];mp[0][0] = 0;mp[0][1] = -prices[0];if (k > 1) {
for (int i = 1; i < k; ++i) {
mp[i][0] = 0;mp[i][1] = Integer.MIN_VALUE;}}for (int i = 1; i < len; i ++) {
for (int j = 0; j <= k; ++j) {
if (j == 0) {
mp[j][0] = mp[0][0];} else {
mp[j][0] = Math.max(mp[j][0], mp[j - 1][1] + prices[i]);}mp[j][1] = Math.max(mp[j][1], mp[j][0] - prices[i]);}}for (int i = 0; i <= k; ++i) {
if (result < mp[i][0]) {
result = mp[i][0];}}return result;}public int greedy(int[] prices) {
int res = 0;for (int i = 1, len = prices.length; i < len; ++i) {
if (prices[i] > prices[i-1]) {
res += prices[i] - prices[i - 1];}}return res;}
}
Review
https://97-things-every-x-should-know.gitbooks.io/97-things-every-programmer-should-know/content/en/thing_02/
Apply Functional Programming Principles
应用函数编程原则
因为比较少接触函数式编程，所以这篇有点没咋看懂。
Tip/Tech
用wireshark进行抓包，分析TCP协议这些。
Share
Can A Computer ‘Own’ Something?
https://medium.com/swlh/can-a-computer-own-something-510295d72f82
在2015年的一项研究中，一种算法能够比你自己的枕边人更好地了解你的个性，如果你在脸书上点了300个你的喜欢。
不由得想起剑桥分析来操纵美国大选的案例：
将来，您的雇主可能是算法。它也可能是你的房东。随着计算机和算法变得越来越复杂，他们拥有东西的想法可能变得不可避免。