Created
May 14, 2023 22:26
-
-
Save Samu31Nd/2f11269ba80f84bd1d4ac97f6e66689b to your computer and use it in GitHub Desktop.
Max Subarray using Divide and Conquer and Kadane algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.Random; | |
| public class Main { | |
| public static void main(String[] args) { | |
| int [] arr1 = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7}; | |
| kadane.max_sum(arr1); | |
| algorithm.init(arr1); | |
| int [] arr2 = algorithm.aleatoryArray(25); | |
| algorithm.init(arr2); | |
| } | |
| static class kadane { | |
| public static void max_sum(int []arr){ | |
| int maxSoFar = 0, | |
| maxEndingHere = 0; | |
| for (int j : arr) { | |
| maxSoFar = j + maxSoFar; | |
| if (maxEndingHere < maxSoFar) { | |
| maxEndingHere = maxSoFar; | |
| } | |
| if (maxSoFar < 0) { | |
| maxSoFar = 0; | |
| } | |
| } | |
| System.out.print("Max sum using Kadane algorithm: " + maxEndingHere + "\n\n"); | |
| } | |
| } | |
| static class algorithm{ | |
| private static int[] aleatoryArray(int n){ | |
| int []arr = new int[n]; | |
| for (int i = 0; i< n; i++) | |
| arr[i] = (int)(new Random().nextFloat(101)) - 50; | |
| return arr; | |
| } | |
| private static int[] FindMaxCrossingSubarray(int[] A, int low, int mid, int high){ | |
| int left_sum = -999999999, | |
| right_sum = -999999999, | |
| max_left = 0, | |
| max_right = 0, | |
| sum = 0; | |
| for (int i = mid; i > low; i--){ | |
| sum += A[i]; | |
| if(sum > left_sum) { | |
| left_sum = sum; | |
| max_left = i; | |
| } | |
| } | |
| sum = 0; | |
| for (int j = mid + 1; j < high; j++){ | |
| sum += A[j]; | |
| if(sum > right_sum) { | |
| right_sum = sum; | |
| max_right = j; | |
| } | |
| } | |
| return new int[]{max_left, max_right, left_sum + right_sum}; | |
| } | |
| private static int [] FindMaximumSubarray(int[]A, int low, int high) { | |
| int mid; | |
| if (high == low) return new int[]{low, high, A[low]}; | |
| else { | |
| mid = ((low + high) / 2); | |
| int[] left = FindMaximumSubarray(A, low, mid); //0: low | |
| //1: high | |
| //2: sum | |
| int[] right = FindMaximumSubarray(A, mid + 1, high); | |
| int[] cross = FindMaxCrossingSubarray(A, low, mid, high); | |
| if (left[2] >= right[2] && left[2] >= cross[2]) return left; | |
| else if (right[2] >= left[2] && right[2] >= cross[2]) return right; | |
| else return cross; | |
| } | |
| } | |
| private static void init(int[]arr){ | |
| System.out.println("Original array: "); | |
| for (int i = 0; i < arr.length; i++){ | |
| System.out.print(" | " + arr[i]); | |
| } | |
| System.out.println(" | " + "\n"); | |
| int [] sol = algorithm.FindMaximumSubarray(arr,0,arr.length - 1); | |
| System.out.println("Maximum SubArray from [" + sol[0] + "] to [" + sol[1] + "] using Divide and Conquer: "); | |
| for (int i = sol[0]; i <= sol[1]; i++){ | |
| System.out.print(" | " + arr[i]); | |
| } | |
| System.out.println(" | "); | |
| System.out.println("With the sum of: " + sol[2] + "\n------------------------------------------------------------------------\n"); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment