题解 | #买卖股票的最好时机(一)#

解题思路（动态规划法）：
以数组price[] = {2, 3, 5, 1, 7}为例，先建立一个数组dp，长度和price相等，由于第一天不能卖出股票，故设置dp[0] = -1 * price[0]；同时设置一个值s_dp = dp[0]用于记录每次卖出的股票值（负数）。

price: 2 3 5 1 7
dp: -2

然后在i = 1到price.length的循环中，若s_dp + prices[i]大于0，则dp[i]的值为s_dp + prices[i]，同时更新最大利润max；若s_dp + prices[i]不大于0，则dp[i]的值为-1 * prices[i]，同时更新s_dp的值为dp[i]：

price: 2 3 5 1 7
dp: -2 1

price: 2 3 5 1 7
dp: -2 1 3

price: 2 3 5 1 7
dp: -2 1 3 -1

price: 2 3 5 1 7
dp: -2 1 3 -1 6

这样便能通过一次遍历，找出最大利润。

代码（java）：

public class Solution {
    public int maxProfit (int[] prices) {
        int[] dp = new int[prices.length];
        dp[0] = -1*prices[0];
        int s_dp = dp[0];
        int max = 0;
        for (int i = 1; i<prices.length; i++) {
            //确定dp[i]的值
            if (s_dp+prices[i]>0) {
                dp[i] = s_dp+prices[i];
                max = Math.max(max, dp[i]);    //更新最大值max
            }
            else {
                dp[i] = -1*prices[i];
                s_dp = dp[i];
            }
        }
        return max;
    }
}