南阳OJ-847 S + T(寻找区间最大差值及其下标)

S + T

时间限制:1000 ms  |  内存限制:65535 KB
难度:2
 
描述

   给你一个长度为n的整数序列A1,A2,……,An,找出两个整数Ai和Aj(i<j),使得Ai-Aj尽量大。

 
输入
输入第一行为数据组数T(T<=100)。每组数据的第一行为整数的个数n(2<=n<=100000);一下n行,每行为一个绝对值不超过150000的正整数。(所有的数据都不超过2^64 - 1)
输出
对于每组数据,输出Ai –Aj的最大值、i值和j值。(如果有多个最大值,则输出先出现的最大值和i,j值)
样例输入
2

3
5 2 1

6
2 3 6 2 1 -1
样例输出
4 1 3
7 3 6
此题用穷举法时间代价为O(n^2),会超过时间限制。所以要用下面这种方法。
#include<stdio.h>
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m, s = -200000;
    scanf("%d", &n);
    scanf("%d", &m);
    int max = m, index = 0, left, right; //index用于记录数组最大值
    for (int i = 1; i < n; i++){  //left,right分别记录下标
      scanf("%d", &m);
      if (max-m > s) {
        s = max-m;
        left = index;
        right = i;
      }
      if (m > max) {//在寻找最大差值的同时,寻找最大值。
        index = i;
        max = m;
      }
    }
    printf("%d %d %d
", s, left+1, right+1);
  }
} 

  

原文地址:https://www.cnblogs.com/Rhett-Q/p/5440349.html