Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class practice {
- public static void main(String[] args){
- int[] a = {9, -3, 7, -12, 3, -2, 5, -8, 8, 13, -20, 6, -4, 3, -5, 3, -2, 18, 9, -4, 5};
- MCSS(a);//this tests the O(n^2)
- MCSS2(a);//this tests the O(n)
- }
- //this tests the O(n^2)
- public static int MCSS(int [] a) {
- int max = 0, sum = 0, start = 0, end = 0;
- int count=0;
- // Try all possible values of start and end indexes for the sum.
- for (int i = 0; i < a.length; i++) {
- sum = 0;
- for (int j = i; j < a.length; j++) {
- sum += a[j]; // No need to re-add all values.
- if (sum > max) {
- count++;
- System.out.printf("Changed max at i= %d and j= %d\n"
- + "\tNew max: %d\n"
- + "\tChanges so far: %d\n", i, j, sum, count);
- max = sum;
- start = i; // Although method doesn't return these
- end = j; // they can be computed.
- }
- }
- }
- System.out.printf("max: %d\n", max);
- return max;
- }
- //this tests the O(n)
- public static int MCSS2(int [] a) {
- int max = 0, sum = 0, start = 0, end = 0, i=0;
- int count = 0;
- // Cycle through all possible end indexes.
- for (int j = 0; j < a.length; j++) {
- sum += a[j]; // No need to re-add all values.
- if (sum > max) {
- count++;
- System.out.printf("Changed max at i=%d and j=%d\n"
- + "\tNew max: %d\n"
- + "\tChanges so far: %d\n", i, j, sum, count);
- max = sum;
- start = i; // Although method doesn't return these
- end = j; // they can be computed.
- }
- else if (sum < 0) {
- i = j+1; // Only possible MCSSs start with an index >j.
- sum = 0; // Reset running sum.
- }
- }
- System.out.printf("max: %d\n", max);
- return max;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement