假设你有一个数组a[n]，其中第 i 个元素是股票在第i天的价格。
你可以买入一次股票和卖出一次股票（并非每天都可以买入或卖出一次，总共只能买入和卖出一次），问能获得的最大收益是多少。
动态规划题目的一般解题步骤：
（1）问题的阶段 （2）每个阶段的状态（3）从前一个阶段转化到后一个阶段之间的递推关系。
这个题目采用一维数组即可
定义一个一维数组dp[]，长度与输入数组大小一致。把dp[i]定义为第i天卖出的最高利润，我们知道最高利润等于第i天的当天股票价格 - 在此之前的最低价格min（也就是我们应该买入的价格）
所以我们可以确定dp数组的公式为：dp[i] = a[i]-min
min初始值我们一般都设为数组的第一项，min = a[0]。而dp[0] = 0,因为第0天只能当天买入，当天卖出。
接下来遍历整个数组，求出每一天出售的最高利润，然后找出最大值即可。
代码：
import java.util.*;
public class Solution {
public int maxProfit (int[] a) {
// write code here
int min = a[0];
int [] dp = new int[a.length];
dp[0] = 0;
int ans = 0;
for(int i=1;i
