What is meant by the maximum sub-array problem is that we want to find the non-empty, contiguous sub-array of an array whose values have the largest sum. Following is a divide & conquer solution implemented for it using Java language.

/** * * @author Rajind */ public class MaximumSubarrayProblem { public static int[] maxSubArray(int[] A) { int newsum = A[0]; int max = A[0]; int low = 0; int high = 0; for(int i=1;i<A.length;i++){ if(newsum+A[i] > A[i]){ high++; }else{ low = i; high = i; } newsum = Math.max(newsum+A[i],A[i]); max= Math.max(max, newsum); } int[] arr = new int[3]; arr[0] = max; arr[1] = low; arr[2] = high; return arr; } public static void main(String args[]){ int[] arr = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7}; int []array = maxSubArray(arr); System.out.println("max: "+array[0]); System.out.println("low: "+array[1]); System.out.println("high: "+array[2]); } }

~Rajind Ruparathna

Advertisements