kodovi/efikasnost-algoritama/MaxNizaPoredjenje.java

   1 import java.util.Scanner;
   2
   3 /**
   4  * Program rešava problem maksimalnog podniza celih brojeva. Tačnije nalazi
   5  * podniz susednih elemenata u nizu koji imaju maksimalnu sumu. Problem je rešen
   6  * na 4 načina različite efikasnosti i dodati su brojači operacija sabiranja da
   7  * bi se dodatno ilustrovale razlike.
   8  */
   9 public class MaxNizaPoredjenje {
  10
  11         static void maxNiza1(int[] niz) {
  12                 int brojOp = 0;
  13                 int max = 0;
  14                 int pocetak = 1, kraj = 1;
  15
  16                 int n = niz.length;
  17
  18                 for (int d = 0; d < n; d++) {
  19                         for (int g = d; g < n; g++) {
  20                                 int suma = 0;
  21                                 for (int i = d; i <= g; i++) {
  22                                         suma = suma + niz[i];
  23                                         brojOp++;
  24                                 }
  25                                 if (suma > max) {
  26                                         max = suma;
  27                                         pocetak = d;
  28                                         kraj = g;
  29                                 }
  30                         }
  31                 }
  32
  33                 System.out.println("Maksimum je " + max + " u intervalu od " + pocetak
  34                                 + " do " + kraj);
  35                 System.out.println("Broj racunskih operacija: " + brojOp);
  36         }
  37
  38         static void maxNiza2(int[] niz) {
  39                 int brojOp = 0;
  40                 int pocetak = 1, kraj = 1;
  41                 int max = 0;
  42
  43                 int n = niz.length;
  44
  45                 int[] pom = new int[n + 1];
  46
  47                 pom[0] = 0;
  48                 for (int i = 1; i < n + 1; i++) {
  49                         pom[i] = pom[i - 1] + niz[i - 1];
  50                         brojOp++;
  51                 }
  52
  53                 for (int d = 0; d < n; d++) {
  54                         for (int g = d; g < n; g++) {
  55                                 int suma = pom[g + 1] - pom[d];
  56                                 brojOp++;
  57                                 if (suma > max) {
  58                                         max = suma;
  59                                         pocetak = d;
  60                                         kraj = g;
  61                                 }
  62                         }
  63                 }
  64
  65                 System.out.println("Maksimum je " + max + " u intervalu od " + pocetak
  66                                 + " do " + kraj);
  67                 System.out.println("Broj racunskih operacija: " + brojOp);
  68         }
  69
  70         static void maxNiza3(int[] niz) {
  71                 int brojOp = 0;
  72                 int max = 0;
  73                 int pocetak = 1, kraj = 1;
  74
  75                 int n = niz.length;
  76
  77                 for (int d = 0; d < n; d++) {
  78                         int suma = 0;
  79                         for (int g = d; g < n; g++) {
  80                                 suma = suma + niz[g];
  81                                 brojOp++;
  82                                 if (suma > max) {
  83                                         max = suma;
  84                                         pocetak = d;
  85                                         kraj = g;
  86                                 }
  87                         }
  88                 }
  89
  90                 System.out.println("Maksimum je " + max + " u intervalu od " + pocetak
  91                                 + " do " + kraj);
  92                 System.out.println("Broj racunskih operacija: " + brojOp);
  93         }
  94
  95         static void maxNiza4(int[] niz) {
  96                 int brojOp = 0;
  97                 int max = 0;
  98                 int pocetak = 1, kraj = 1;
  99
 100                 int n = niz.length;
 101
 102                 int maxDovde = 0;
 103
 104                 int d = 0;
 105                 for (int i = 0; i < n; i++) {
 106                         if (maxDovde == 0) {
 107                                 d = i;
 108                         }
 109                         maxDovde = maxDovde + niz[i];
 110                         brojOp++;
 111                         if (maxDovde < 0) {
 112                                 maxDovde = 0;
 113                         }
 114
 115                         if (maxDovde > max) {
 116                                 max = maxDovde;
 117                                 pocetak = d;
 118                                 kraj = i;
 119                         }
 120                 }
 121
 122                 System.out.println("Maksimum je " + max + " u intervalu od " + pocetak
 123                                 + " do " + kraj);
 124                 System.out.println("Broj racunskih operacija: " + brojOp);
 125         }
 126
 127         static void stampajNiz(int[] niz) {
 128                 System.out.println("Duzina niza: " + niz.length);
 129                 for (int i = 0; i < niz.length; i++) {
 130                         System.out.println(i + " " + niz[i]);
 131                 }
 132         }
 133
 134         static int[] ucitajNiz() {
 135                 Scanner in = new Scanner(System.in);
 136                 System.out.print("Unesite broj brojeva u nizu X:");
 137                 int n = in.nextInt();
 138                 int[] niz = new int[n];
 139
 140                 System.out.print("Unesite niz x:");
 141                 for (int i = 0; i < n; i++) {
 142                         niz[i] = in.nextInt();
 143                 }
 144                 in.close();
 145
 146                 return niz;
 147         }
 148
 149         public static void main(String[] args) {
 150                 int[] niz = ucitajNiz();
 151
 152                 stampajNiz(niz);
 153                 System.out.println();
 154
 155                 System.out.println("Metod 1: ");
 156                 maxNiza1(niz);
 157                 System.out.println();
 158
 159                 System.out.println("Metod 2: ");
 160                 maxNiza2(niz);
 161                 System.out.println();
 162
 163                 System.out.println("Metod 3: ");
 164                 maxNiza3(niz);
 165                 System.out.println();
 166
 167                 System.out.println("Metod 4: ");
 168                 maxNiza4(niz);
 169         }
 170 }