Izpitno vprašanje RAČ2PRA 3100

Iz MaFiRaWiki

Vprašanje

Sestavi javno statično metodo, ki za dano tabelo celih števil vrne maksimalno vsoto podzaporedja. Pri tem uporabi algoritem časovne zahtevnosti O(n). Razloži, kako bi poiskal VSA podzaporedja z maksimalno vsoto.

Odgovor

Metoda za iskanje maksimalnega podzaporedja

  1. public static int borznikO(int[] a) {
  2. //algoritem casovne zahtevnosti O(n)
  3. //vrača vsoto optimalnega podzaporedja
  4. int opt = 0;
  5. int n = a.length;
  6. int s = 0;
  7. for (int i = 0; i < n; i++) {
  8. // i - kje se konca!
  9. int t = s + a[i];
  10. if (t > 0) { // ce je vsota "se > 0, se i-tega splaca vzeti
  11. s = t;
  12. if (s > opt) // nasli smo boljso
  13. opt = s;
  14. }
  15. else { // drugace raje zacnemo na novo
  16. s = 0;
  17. }
  18. }
  19. return opt;
  20. }

Vsa maksimalna podzaporedja lahko poiščemo tako, da najprej poiščemo maksimalno vsoto podzaporedja in prešetejemo kolikokrat se le ta še pojavi. Na drugem koraku pa poiščemo vse začetke in konce teh podzaporedij.

Metoda, ki nam vrne vse začetke in konce optimalnega (maksimalnega) podzaporedja.

  1. public static int[][] borznikOa(int[] a) {
  2. //algoritem casovne zahtevnosti O(n)
  3. //vrača vsoto optimalnega podzaporedja
  4. // odDo[0] : za"ceteki odDo[1] pa konci podzaporedja!
  5. int opt = 0;
  6. int n = a.length;
  7. int s = 0;
  8. int kolikokrat = 0;
  9. int tr_zacetek = 0; // trenutni zacetek zaporedja
  10. // poi"s"cemo optimalno podzaporedje in pre"stejemo koliko jih je
  11. for (int i = 0; i < n; i++) {
  12. // i - kje se konca!
  13. int t = s + a[i];
  14. if (t > 0) { // ce je vsota "se > 0, se i-tega splaca vzeti
  15. s = t;
  16. if (s >= opt) // nasli smo boljso
  17. if(s == opt){
  18. kolikokrat++;
  19. } else {
  20. opt = s;
  21. kolikokrat=1;
  22. }
  23. }
  24. else { // drugace raje zacnemo na novo
  25. s = 0;
  26. }
  27. }
  28. int[][] odDo = new int [2][kolikokrat];
  29. s = 0;
  30. int nasli=0;
  31. for (int i = 0; i < n; i++) {
  32. // i - kje se konca!
  33. int t = s + a[i];
  34. if (t > 0) { // ce je vsota "se > 0, se i-tega splaca vzeti
  35. s = t;
  36. if (s == opt){ // nasli smo re"sitev, zato jo dodamo v tabelo
  37. odDo[0][nasli] = tr_zacetek;
  38. odDo[1][nasli] = i;
  39. nasli++;
  40. }
  41. }
  42. else { // drugace raje zacnemo na novo
  43. s = 0;
  44. tr_zacetek = i + 1;
  45. }
  46. }
  47. return odDo;
  48. }

Resnici na ljubo bi lahko prvi in drugi korak združili. Sproti bi torej iskali maksimalno vosto in tabelo koncev, kjer jo dosežemo. Le paziti bi morali, da vedno, kadar najdemo boljše podzaporedje, tabelo začetkov in koncev začnemo polniti znova!

Osebna orodja