Advertisement
DulcetAirman

Maximale Teilsumme

Jun 11th, 2012
136
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package ch.fhnw.claudemartin.algd1.maxteilsumme;
  2.  
  3. import java.util.Arrays;
  4. import java.util.Random;
  5. import java.util.concurrent.atomic.AtomicInteger;
  6.  
  7. public class MaxT {
  8.  
  9.   static int naive(byte[] a) {
  10.     int sum = 0;
  11.     int x;
  12.  
  13.     loop1: for (int left = 0; left < a.length; left++) {
  14.       while (a[left] <= 0)
  15.         continue loop1;
  16.       loop2: for (int right = a.length - 1; right >= left; right--) {
  17.         while (a[right] <= 0)
  18.           continue loop2;
  19.         x = 0;
  20.         for (int i = left; i <= right; i++) {
  21.           x += a[i];
  22.         }
  23.         if (x > sum)
  24.           sum = x;
  25.       }
  26.     }
  27.     return sum;
  28.   }
  29.  
  30.   public static void main(String[] args) {
  31.  
  32.     test(new byte[] { 42 });// 42
  33.     test(new byte[] { -1, 0, 1 });// 1
  34.     test(new byte[] { 1, 0, 1 });// 2
  35.     test(new byte[] { 1, 1, 1 });// 3
  36.     test(new byte[] { -1 });// 0
  37.     test(new byte[] { 10, 21, -13, 7, 9, -4, -9, 21, -6, 13, 17, 12, 1, -7, -6, 9 });// 79
  38.     test(new byte[] { 31, -41, 59, 26, -53, 58, 97, -93, -23, 84 });// 187
  39.  
  40.     for (int i = 0; i < 10; i++) {
  41.       test(1000 + i);
  42.     }
  43.  
  44.     for (int i = 0; i < 10; i++) {
  45.       test((int) Math.pow(10, i));
  46.     }
  47.   }
  48.  
  49.   static int seed = 0;
  50.  
  51.   private static void test(int n) {
  52.     Random random = new Random(seed++);
  53.     final byte[] a = new byte[n];
  54.     for (int i = 0; i < a.length; i++) {
  55.       a[i] = (byte) ((random.nextDouble() - 0.5) * Byte.MAX_VALUE);
  56.     }
  57.     test(a);
  58.   }
  59.  
  60.   private static void test(final byte[] a) {
  61.  
  62.     // int[] a = { 2, -1, 3 };
  63.     // System.out.println(Arrays.toString(a));
  64.     long start = System.currentTimeMillis();
  65.     final int maxT = maxTeilsumme(a);
  66.     long end = System.currentTimeMillis();
  67.     System.out.println("length: " + a.length);
  68.     System.out.println("result: " + maxT);
  69.     System.out.println("time (ms): " + (end - start));
  70.  
  71.     if (a.length <= 5000) {
  72.       final long s = System.currentTimeMillis();
  73.       int naive = naive(a);
  74.       if (maxT != naive) {
  75.         System.err.println("Wrong result!!!");
  76.         System.err.println("Naive result: " + naive);
  77.         System.err.println("Array: " + Arrays.toString(a));
  78.       }
  79.       System.out.println("time of naive impl. (ms): " + (System.currentTimeMillis() - s));
  80.     }
  81.     System.out.println("----------------");
  82.   }
  83.  
  84.   static int maxTeilsumme(final byte[] a) {
  85.     if (a.length == 0)
  86.       return 0;
  87.     final int left = 0;
  88.     final int right = a.length - 1;
  89.     // erst bei sehr grossen Arrays lohnt sich Multithreading:
  90.     if (a.length < 1000000)
  91.       return maxTeilsumme(a, left, right);
  92.     // else:
  93.  
  94.     // System.out.println(left+", "+right);
  95.     final int m = left + ((right - left) >> 1);
  96.     assert m > left && m < right;
  97.  
  98.     final AtomicInteger vLsum = new AtomicInteger();
  99.     Thread t1 = new Thread() {
  100.       public void run() {
  101.         vLsum.set(maxTeilsumme(a, left, m));
  102.       };
  103.     };
  104.  
  105.     final AtomicInteger vRsum = new AtomicInteger();
  106.     Thread t2 = new Thread() {
  107.       public void run() {
  108.         vRsum.set(maxTeilsumme(a, m + 1, right));
  109.       };
  110.     };
  111.  
  112.     final AtomicInteger asum = new AtomicInteger();
  113.     Thread t3 = new Thread() {
  114.       public void run() {
  115.         asum.set(sum(a, left, right));
  116.       };
  117.     };
  118.  
  119.     t1.start();
  120.     t2.start();
  121.     t3.start();
  122.  
  123.     try {
  124.       t1.join();
  125.       t2.join();
  126.       t3.join();
  127.     } catch (InterruptedException e) {
  128.       e.printStackTrace();
  129.     }
  130.  
  131.     return max(vLsum.get(), vRsum.get(), asum.get());
  132.  
  133.   }
  134.  
  135.   static int maxTeilsumme(final byte[] a, final int left, final int right) {
  136.     assert right >= left;
  137.     // System.out.println(left+", "+right);
  138.     switch (right - left) {
  139.     case 0:
  140.       return a[left] > 0 ? a[left] : 0;
  141.     case 1:
  142.       return max(0, a[left], a[right], a[left] + a[right]);
  143.     case 2:
  144.       final int lft = a[left];
  145.       final int mid = a[right - 1];
  146.       final int rgt = a[right];
  147.       return max(0, lft, mid, rgt, a[left] + mid, mid + a[right], a[left] + mid + a[right]);
  148.     case 3:
  149.       final int a1 = a[left];// right-3
  150.       final int a2 = a[left + 1];// right-2
  151.       final int a3 = a[right - 1];// left+2
  152.       final int a4 = a[right];// left+3
  153.       final int a12 = a1 + a2;
  154.       final int a34 = a3 + a4;
  155.       return max(0, a1, a2, a3, a4, a12, a2 + a3, a34, a12 + a3, a2 + a34, a12 + a34);
  156.     default:
  157.       int m = left + ((right - left) >> 1);
  158.       assert m > left && m < right;
  159.       int vLsum = maxTeilsumme(a, left, m);
  160.       int vRsum = maxTeilsumme(a, m + 1, right);
  161.       int asum = sum(a, left, right);
  162.       return max(vLsum, vRsum, asum);
  163.     }
  164.   }
  165.  
  166.   static int sum(byte[] a, int left, int right) {
  167.     int sum = 0;
  168.     int rmax = 0;
  169.     int m = left + ((right - left) >> 1);
  170.     for (int i = m + 1; i <= right; i++) {
  171.       sum += a[i];
  172.       if (sum > rmax)
  173.         rmax = sum;
  174.     }
  175.     sum = 0;
  176.     int lmax = 0;
  177.     for (int i = m; i >= left; i--) {
  178.       sum += a[i];
  179.       if (sum > lmax)
  180.         lmax = sum;
  181.     }
  182.     return lmax + rmax;
  183.   }
  184.  
  185.   static int max(int... vals) {
  186.     assert vals.length > 0;
  187.     int rv = Integer.MIN_VALUE;
  188.     for (int i : vals) {
  189.       if (i > rv)
  190.         rv = i;
  191.     }
  192.     assert rv != Integer.MIN_VALUE;
  193.     return rv;
  194.   }
  195.  
  196. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement