找到数组中最大丢落的算法

5 回答

• 5

  创建新的2个数组：

  max[i] = max { arr[0], arr[1], ..., arr[i] }
  min[i] = min { arr[n-1], arr[n-2], ..., arr[i] }
  (max is the maximum from first to i, min is the minimum from i to last)
  

  现在，迭代辅助阵列并找到最大差异 max[i] - min[i]

  这需要总共3次迭代，因此 O(n) .

  Proof of correctness (guidelines):

  让最大的下降是从索引 i 到索引 j ，其中 i<j ：

  • 然后， max[i] >= arr[j] （因为我们已经通过了它），以及 min[i] <= arr[i] - 因此 max[j] - min[j] >= arr[i] - arr[j] ，算法提供的答案至少和最优答案一样好 .

  • 另外，由于最大跌幅是 i,j ，因此不能有 k<j 这样的 arr[k] < arr[i] ，因为那时最大跌幅将是从 arr[k] 到 arr[j] . 相似 - 由于同样的原因， arr[k] < arr[j] 不能 k>j ，因而 max[j]-min[j] <= arr[i] - arr[j]

  从上面我们可以得出结论 max[j]-min[j] = arr[i] - arr[j] . 所有留给一个正式的完整证明是显示每个 k 你得到 max[k]-min[k] <= max[j] - min[j] ，这确实是这样，否则有一些 u<k ， v>k 这样 max[k]=arr[u], min[k]=arr[v] ，你得到 arr[u] - arr[v] > arr[i] - arr[j] ，这与 i,j 是的事实相矛盾最大跌幅 .

  QED

  回复于 2024-04-21T00:27:27+08:00
• -1

  你需要跟踪两件事：

  您所拥有的最大数量似乎是元素i，并且相对于最大数字（即i之前的最大数量减去元素i），您看起来最大的数量 . 这将是O（n）的时间和O（1）的空间 .

  这个问题正是"stock buying/selling"面试的问题，解决方法可以在这里找到：Maximum single-sell profit

  回复于 2024-04-21T00:27:27+08:00
• -1

  没有额外空间的O（n）解决方案：

  public int maxDrop(int[] a) {
      int max = a[0];
      int maxDrop = -1;
      for (int i = 0; i < a.length; i++) {
          if (max < a[i]) {
              max = a[i];
          }
          else {
              int drop = max - a[i];
              maxDrop = Math.max(maxDrop, drop);
          }
      }
      return maxDrop;
  }
  

  回复于 2024-04-21T00:27:27+08:00
• 3

  我只能想到O（nlogn）但是这个虽然相同的复杂性应该比排序和找到最大的下降更快 .

  你可以做的是计算O（n）中连续数字的差异然后问题将减少到找到连续子数组的MAX（和），这将是O（nlogn）

  回复于 2024-04-21T00:27:27+08:00
• 4

  public static int maxDrop(int[]array){
  
      int maxDrop =0,drop=0,min=array[0];
  
      for(int i=1;i<array.length;i++){
  
          if(array[i]<min){
              min=array[i];
          }
  
          drop = array[i]-min;
  
          if(drop>maxDrop){
              maxDrop=drop;
          }
  
      }
  
      System.out.println(maxDrop);
      return maxDrop;
  
  }
  

  回复于 2024-04-21T00:27:27+08:00