# 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();
100.       public void run() {
101.         vLsum.set(maxTeilsumme(a, left, m));
102.       };
103.     };
104.
105.     final AtomicInteger vRsum = new AtomicInteger();
107.       public void run() {
108.         vRsum.set(maxTeilsumme(a, m + 1, right));
109.       };
110.     };
111.
112.     final AtomicInteger asum = new AtomicInteger();
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. }