demo
Class Pnouseva

java.lang.Object
  demo.Pnouseva

public class Pnouseva
extends java.lang.Object

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 nykyistä ennätystä ei voi parantaa.

  Huomautti Vesa Lappalainen 19.3.1998
 

Version:

1.0, 09.03.2003

Author:

Vesa Lappalainen

Constructor Summary

Pnouseva()

Method Summary

static void	main(java.lang.String[] args) Testataan pisinNouseva-aliohjelmaa
static int	nouseva(java.lang.String jono, int alku) Etsitään kuinka monta peräkkäistä "nousevaa" merkkiä on alkaen paikasta alku.
static int	pisinNouseva(java.lang.String jono) Etsitään pisimmän nousevan osajonon pituus merkkijonosta

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Pnouseva

public Pnouseva()

Method Detail

nouseva

public static int nouseva(java.lang.String jono,
                          int alku)

Etsitään kuinka monta peräkkäistä "nousevaa" merkkiä on alkaen paikasta alku.

Parameters:

jono - merkkijonojota tutkitaan

alku - paikka josta aloitetaan

Returns:

peräkkäisten nousevien merkkien määrä

Example:

 nouseva("",0)    === 1;
 nouseva("a",0)   === 1;
 nouseva("aa",0)  === 2;
 nouseva("aab",0) === 3;
 nouseva("bab",0) === 1; // NOPMD
 nouseva("bab",1) === 2;
 nouseva("bab",2) === 1;
 nouseva("bab",3) === 1;
 

pisinNouseva

public static int pisinNouseva(java.lang.String jono)

Etsitään pisimmän nousevan osajonon pituus merkkijonosta

Parameters:

jono - tutkittava merkkijono

Returns:

pisimmän nousevan osajonon pituus

Example:

 pisinNouseva("abajiuxc") === 3;
 pisinNouseva("kissa")    === 3;  
 pisinNouseva("abcdefg")  === 7;
 pisinNouseva("dcba")     === 1;
 pisinNouseva("ab")       === 2;
 pisinNouseva("a")        === 1;
 pisinNouseva("")         === 0;
 

main

public static void main(java.lang.String[] args)

Testataan pisinNouseva-aliohjelmaa

Parameters:

args - ei käytössä