Maximale Teilsumme

package ch.fhnw.claudemartin.algd1.maxteilsumme;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.atomic.AtomicInteger;

public class MaxT {

  static int naive(byte[] a) {
    int sum = 0;
    int x;

    loop1: for (int left = 0; left < a.length; left++) {
      while (a[left] <= 0)
        continue loop1;
      loop2: for (int right = a.length - 1; right >= left; right--) {
        while (a[right] <= 0)
          continue loop2;
        x = 0;
        for (int i = left; i <= right; i++) {
          x += a[i];
        }
        if (x > sum)
          sum = x;
      }
    }
    return sum;
  }

  public static void main(String[] args) {

    test(new byte[] { 42 });// 42
    test(new byte[] { -1, 0, 1 });// 1
    test(new byte[] { 1, 0, 1 });// 2
    test(new byte[] { 1, 1, 1 });// 3
    test(new byte[] { -1 });// 0
    test(new byte[] { 10, 21, -13, 7, 9, -4, -9, 21, -6, 13, 17, 12, 1, -7, -6, 9 });// 79
    test(new byte[] { 31, -41, 59, 26, -53, 58, 97, -93, -23, 84 });// 187

    for (int i = 0; i < 10; i++) {
      test(1000 + i);
    }

    for (int i = 0; i < 10; i++) {
      test((int) Math.pow(10, i));
    }
  }

  static int seed = 0;

  private static void test(int n) {
    Random random = new Random(seed++);
    final byte[] a = new byte[n];
    for (int i = 0; i < a.length; i++) {
      a[i] = (byte) ((random.nextDouble() - 0.5) * Byte.MAX_VALUE);
    }
    test(a);
  }

  private static void test(final byte[] a) {

    // int[] a = { 2, -1, 3 };
    // System.out.println(Arrays.toString(a));
    long start = System.currentTimeMillis();
    final int maxT = maxTeilsumme(a);
    long end = System.currentTimeMillis();
    System.out.println("length: " + a.length);
    System.out.println("result: " + maxT);
    System.out.println("time (ms): " + (end - start));

    if (a.length <= 5000) {
      final long s = System.currentTimeMillis();
      int naive = naive(a);
      if (maxT != naive) {
        System.err.println("Wrong result!!!");
        System.err.println("Naive result: " + naive);
        System.err.println("Array: " + Arrays.toString(a));
      }
      System.out.println("time of naive impl. (ms): " + (System.currentTimeMillis() - s));
    }
    System.out.println("----------------");
  }

  static int maxTeilsumme(final byte[] a) {
    if (a.length == 0)
      return 0;
    final int left = 0;
    final int right = a.length - 1;
    // erst bei sehr grossen Arrays lohnt sich Multithreading:
    if (a.length < 1000000)
      return maxTeilsumme(a, left, right);
    // else:

    // System.out.println(left+", "+right);
    final int m = left + ((right - left) >> 1);
    assert m > left && m < right;

    final AtomicInteger vLsum = new AtomicInteger();
    Thread t1 = new Thread() {
      public void run() {
        vLsum.set(maxTeilsumme(a, left, m));
      };
    };

    final AtomicInteger vRsum = new AtomicInteger();
    Thread t2 = new Thread() {
      public void run() {
        vRsum.set(maxTeilsumme(a, m + 1, right));
      };
    };

    final AtomicInteger asum = new AtomicInteger();
    Thread t3 = new Thread() {
      public void run() {
        asum.set(sum(a, left, right));
      };
    };

    t1.start();
    t2.start();
    t3.start();

    try {
      t1.join();
      t2.join();
      t3.join();
    } catch (InterruptedException e) {
      e.printStackTrace();
    }

    return max(vLsum.get(), vRsum.get(), asum.get());

  }

  static int maxTeilsumme(final byte[] a, final int left, final int right) {
    assert right >= left;
    // System.out.println(left+", "+right);
    switch (right - left) {
    case 0:
      return a[left] > 0 ? a[left] : 0;
    case 1:
      return max(0, a[left], a[right], a[left] + a[right]);
    case 2:
      final int lft = a[left];
      final int mid = a[right - 1];
      final int rgt = a[right];
      return max(0, lft, mid, rgt, a[left] + mid, mid + a[right], a[left] + mid + a[right]);
    case 3:
      final int a1 = a[left];// right-3
      final int a2 = a[left + 1];// right-2
      final int a3 = a[right - 1];// left+2
      final int a4 = a[right];// left+3
      final int a12 = a1 + a2;
      final int a34 = a3 + a4;
      return max(0, a1, a2, a3, a4, a12, a2 + a3, a34, a12 + a3, a2 + a34, a12 + a34);
    default:
      int m = left + ((right - left) >> 1);
      assert m > left && m < right;
      int vLsum = maxTeilsumme(a, left, m);
      int vRsum = maxTeilsumme(a, m + 1, right);
      int asum = sum(a, left, right);
      return max(vLsum, vRsum, asum);
    }
  }

  static int sum(byte[] a, int left, int right) {
    int sum = 0;
    int rmax = 0;
    int m = left + ((right - left) >> 1);
    for (int i = m + 1; i <= right; i++) {
      sum += a[i];
      if (sum > rmax)
        rmax = sum;
    }
    sum = 0;
    int lmax = 0;
    for (int i = m; i >= left; i--) {
      sum += a[i];
      if (sum > lmax)
        lmax = sum;
    }
    return lmax + rmax;
  }

  static int max(int... vals) {
    assert vals.length > 0;
    int rv = Integer.MIN_VALUE;
    for (int i : vals) {
      if (i > rv)
        rv = i;
    }
    assert rv != Integer.MIN_VALUE;
    return rv;
  }

}