/*Ylesanne p2rineb 2004 a koolilaste informaatika olympiaadi l6ppvoorust.
 * On antud arvude jada ja on vaja leida k6ige pikem vahe kahe arvu vahel, 
 * kus 1. arv on suurem teisest arvust, st k6ik vahepealsed arvud peavad 
 * 1. arvust v2iksemad olema. Originaalis oli juttu lauam2ngust ridakabe
 * ja küsiti kui kaugele saab nupuga hüpata, kui nupp "ületab" vaid endast
 * madalamaid nuppe.
 * Näide demonstreerib ülesande lahendust ruutkeerukusega
 */
#include <stdio.h>
#include <time.h>
#define MaxN 100
main(){
  int a[MaxN];
  int i,j,k;
  int alg, lopp, on, e, v;
  time_t now, now1;
  struct tm *time_now, *time_now1;
  srand(time(0));
  for (i=0; i<MaxN; i++) {
     a[i]=rand()%100; //  Juhuslikud arvud 0 .. 99
  }
  for (i=0; i<MaxN; i++) {
     printf("%d ",a[i]);
     }
  now = time(0);
  time_now = localtime(&now);
  lopp=0;
  alg=0;
  for (i=0; i<MaxN-1; i++) {
          e=i; v=i;      //Fikseerime 1. ja viimase
          while (v<MaxN) {           // Ja hakkame viimast edasi nihutama kui esimesest väiksem arv seda lubab.
               if (a[e]>a[v]) {
                  v++;
               }
               else {
                    if (lopp-alg<v-e) {
                         lopp=v; alg=e;
                    }
                    e=v;
                    v++;
               }
          }
          if (lopp-alg<v-e) {
               lopp=v; alg=e;
          }
  }
  now1 = time(0);
  time_now1 = localtime(&now1);
  printf("\nRuutkeerukus. Arve %d\n",MaxN);
  printf("Algus %d\n",time_now->tm_sec);
  printf("Lõpp %d\n",time_now1->tm_sec);
  printf("Kestvus %d\n",now1-now);
  printf("Pikim vahe on algusega %d ja lopuga %d",alg,lopp);

}