数据结构（day12）

根据问题分析我们得知这是求取最优子结构的情况--因此使用动态分析

动态分析的四个步骤是

状态定义：定义一个int max存储最大利润    定义一个int cost  存取最小的值
转移方程：   

   max=Math.max(max,第i日价钱-cost)

   前i日最大利润=max(前(i−1)日最大利润,第i日价格−前i日最低价格（cost）)

初始状态： 数组为0的时候  利润为0
返回值： max就是最大的利润

例如 示例1  

   7的时候最小cos为7 max为0

   1的时候最小cos为1   因为1-7<0 所以max为0

   5的时候最小的cos还是为1   max为4

   3的时候最小的cos为1 max为4

   6的时候最小的cos为1 max为5

  4的时候最小的cos为1 max为5

最后遍历完毕得到max为5

  

   示例2

7的时候cos为7  max为0

6的时候cos为6 max为0

4的时候cos为4 max为0

3的时候cos为3 max为0

1的时候cos为1 max为0

最后遍历完毕 输出max为0

     

class Solution {
    public int maxProfit(int[] prices) {
        int max=0; //最大利润
        int cost=Integer.MAX_VALUE;
        for(int price:prices){
            cost=Math.min(cost,price);//取到那个是最小  //即买的时候最小的时候
            max=Math.max(max,price-cost);//在值最大的时候卖出
        }
        return max;
    }
}

根据问题分析我们得知这是求取最优子结构的情况--因此使用动态分析

动态分析的四个步骤是

nums为问题的输入数组

状态定义：定义一个int res为最大值  初始化为数组nums[0]
转移方程：   

    1.我们知道求得最大的值 即大于0即可

       nums[i]+=max(nums[i-1],0)  -->当nums[i-1]为负数的时候直接等于本身 

                                                       当nums[i-1]为整数的时候直接加上 

                这样就保证了值总是最大的

    2.然后就跟res进行比较  选出最大的

        res=max（res，nums[i]）

初始状态：数组只有一个值的时候  直接返回nums[0]
返回值： res最大的值

例如：示例1

我们从索引为1开始遍历   因为我们使用了nums[i-1]放置出现数组越界问题

1的时候 nums[0]<0 nums[1]=1  max=1

-3的时候 nums[1]>0 nums[2]=-3+1=-2  max=1

4的时候 nums[2]<0 nums[3]=4  max=4

-1的时候nums[3]>0 nums[4]=-1+4=3 max=4

2的时候 nums[4]>0 nums[5]=2+3=5 max=5

1的时候 nus[5]>0 nums[6]=1+5=6 max=6

-5的时候 nums[6]>0 nums[7]=-5+6=1 max=6

4的时候 nums[7]>0 nums[8]=4+1=5 max=5

最后得到max为6

class Solution {
    public int maxSubArray(int[] nums) {
    int res = nums[0];  //默认nums[0]为最大值
        for(int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);  //如果大于0就加  否则就是本身
            res = Math.max(res, nums[i]);  //进行比较  选出最大
        }
        return res;

    }
}