/* pnouseva.cpp */
/*
Palauttaa merkkijonosta pisimm„n pelk„st„„n kasvavan (samoja tai aakkosissa
aina edelt„j„„ns„ "suurempia" merkkej„ sis„lt„v„n) merkkijoukon pituuden.

Algoritmi:
==========

Tutkitaan merkkijonon jokaisen merkin kohdalta, kuinka pitk„ jono
siit„ eteenp„in on kasvavia merkkej„ ja palutetaan pisimm„n
l”ytyneen kasvavan jonon pituus.

0. Menn„„n jonon alkuun.
1. Jos ollaan lopussa palautetaan pisimm„n l”ytyneen kasvavan
   jonon pituus ja lopetetaan.
2. Tutkitaan kuinka pitk„ kasvava jono alkaa kohdalla olevasta
   merkist„.
3. Jos kasvava jono on pitempi kuin t„h„nastinen pisin, niin
   merkataan t„m„ pisimm„ksi.
4. Menn„„n siihen merkkiin, johon edellinen kasvava jono p„„ttyi
   ja jatketaan kohdasta 1.


Syyllinen: Mikko Puhalainen, 18.3.1999

Esim jos
  0123456789
  abcdabcdea
kohdasta 0 kysyt„„n nousevan pituutta saadaan 4.  Jos kohdasta 1 kysyt„„n
nousevan pituutta, saadaan 3, kohdasta 2=>2, 3=1.
Vasta kohdasta 4 alkaen voi tulos j„lleen parantua.
Eli siksi loikan pituus kannattaa olla nousevan pituus

Viel„ v„h„n voisi optimoida lopettamalla haku jo ennen jonon p„„ttymist„,
jos nyksyit„ enn„tyst„ ei voi parantaa.

Huomautti Vesa Lappalainen 19.3.1998

*/

#include <iostream.h>

#if 0

int nouseva(const char *p)
{
  int i, pituus = 1;
  if ( p[0] == 0 ) return 0;
  for (i=0; p[i+1]; i++)
    if ( p[i] <= p[i+1] ) pituus++;
    else break;

  return pituus;
}

int pisin_nouseva(const char *jono)
/* Etsi virhe t„st„ funktiosta :-) Huom: vl */
{
  int i, pisin = 0, pituus = 1;

  for (i=0; jono[i]; i+=pituus) {
    pituus = nouseva(jono+i);
    if ( pisin < pituus ) pisin = pituus;
  }
  return pisin;
}

#endif

#if 1

#include <string>
using namespace std;

int nouseva(const string &jono,int alku=0)
{
  int i, pituus = 1, jono_pit = jono.length();
  for (i=alku; i<jono_pit-1; i++)
    if ( jono[i] <= jono[i+1] ) pituus++;
    else break;

  return pituus;
}

int pisin_nouseva(const string &jono)
{
  int i, pisin = 0, pituus = 1, jono_pit = jono.length();

  for (i=0; i<jono_pit; i+=pituus) {
    pituus = nouseva(jono,i);
    if ( pisin < pituus ) pisin = pituus;
  }
  return pisin;
}

#endif

int main(void)
{
  cout << "---" << endl;
  cout << pisin_nouseva("abajiuxc") << endl;
  cout << pisin_nouseva("kissa") << endl;
  cout << pisin_nouseva("abcdefg") << endl;
  cout << pisin_nouseva("dcba") << endl;
  cout << pisin_nouseva("ab") << endl;
  cout << pisin_nouseva("a") << endl;
  cout << pisin_nouseva("") << endl;

  return 0;
}