package dynamic;

/**
 * 题目:股票买卖的最大利润
 * 例如:
 * [9,8,7,5,1,8] 这个股票在1位置买入,在8位置卖出是是最大利润7
 * [9,8,7,6] 这个股票由于是一直在跌,所以没有利润
 * @Author Gavin
 * @date 2022年05月02日 22:44
 */
public class solution_10 {
 /**
 * 第一种方式:暴力破解
 * 双层循环,处理数组中的任意数字组合
 *
 */
 //Time:O(n^2),Space:O(1)
 public int solution(int[] arr){
 if(arr.length<2)return 0;
 int max=0;
 for (int i = 0; i < arr.length; i++) {
 for (int j = i+1; j < arr.length; j++) {
 max=Math.max(max,arr[j]-arr[i]);
 }
 }
 return max;
 }
 /**
 * 第二种方式,动态规划
 */
 //Time:O(1),Space:O(1)
 public int solution_2(int[] arr){
 if(arr.length<2)return 0;
 int max=0,buyMin=arr[0];
 for (int i = 1; i < arr.length; i++) {
 if(arr[i]<buyMin)buyMin=arr[i];
 else{
 max=Math.max(max,arr[i]-buyMin);
 }
 }
 return max;
 }
}