题目描述

有一个长为n的数组A,求满足0≤a≤b<n的A[b]-A[a]的最大值。

给定数组A及它的大小n,请返回最大差值。

测试样例:

[10,5],2

返回:

0

2 1 收藏


直接登录
最新评论
  • 王念一 高二学生 2017/04/21

    遍历记录符合条件最值,复杂度 O(n)。

    (为什么最近的题好没技术含量啊orz)

    • 王念一 高二学生 2017/04/21

       

      • 王念一 高二学生 2017/04/21

        orz 那行 return {min: min, max: max} 要放在 forEach() 后面,论直接在代码框里敲代码不运行的坏处。。

      • 紫烟   2017/05/22

        你这个只是找到了最大值和最小值吧,后面一个没看懂。

        但条件是0≤a≤b<n的A[b]-A[a]的最大值,也就是右边的数字减去左边的数字的最大差值

  • 浣熊、 小学一年级 2017/04/21

     

  • 紫烟   2017/05/22

     

  • 这个不是LeetCode 买卖股票最里面第一个最简单的题目么:

    直接一维dp搞定:

    int findthemax(vector<int> input){

    int len = input.size();

    dp[0] = 0;

    int min = input[0];

    int max_profit=0;

    for(int i=1; i<len; i++){

    if(input[i]<min){

    min = input[i];

    }

    else{

    dp[i] = max(profit,input[i]-min);

    }

    }

    return dp[len-1];

    }