maximum subarray


See On Github

Data

Tags

Source Code

/*
 * Written by: Rafael A. Rivera
 * Last Updated: December 30, 2013
 */

public class Maximum_Subarray {
	
	/*
	 * Description:
	 * 		Finds a subarray with the maximum sum. We refer to it as "a subarray" because there might
	 * be others that have the same sum. We take a "divide and conquer" approach in which the array is
	 * divided in half and the individual subproblems are solved.  
	 * 
	 * Input:
	 * 		array:double - a sequence of numbers.
	 * 		low:int - index of the first element (inclusive).
	 * 		hight:int - index of the last element (inclusive).
	 * 
	 * Output:
	 * 		A tuple that consists of the following values (leftIndex, rightIndex, sum).
	 * 	In the tuple, leftIndex and rightIndex is the range of the subarray.
	 *
	 * Complexity:
	 * 		O(nlog(n))
	 */
	public static Tuple<Integer,Integer,Double> maxSubarray(double[] array, int low, int high){
		
		if(high == low){
			return new Tuple<Integer,Integer,Double>(low, high, array[low]);
			
		}else{
			int mid = (low+high)/2;
			
			Tuple<Integer,Integer,Double> maxLeft = maxSubarray(array,low,mid);
			Tuple<Integer,Integer,Double> maxRight = maxSubarray(array,mid+1,high);
			Tuple<Integer,Integer,Double> maxCross = maxCrossingSubarray(array,low,mid,high);
			
			if(maxLeft.getZ() >= maxRight.getZ() && maxLeft.getZ() >= maxCross.getZ()){
				return maxLeft;
			}else if(maxRight.getZ() >= maxRight.getZ() && maxRight.getZ() >= maxCross.getZ()){
				return maxRight;
			}else{
				return maxCross;
			}
		}
	}
	
	private static Tuple<Integer,Integer,Double> 
			maxCrossingSubarray(double[] array, int low, int mid, int high){
		
		int sum = 0;
		
		double leftSum = Double.NEGATIVE_INFINITY;
		int maxLeft = -1;
		
		for(int i = mid; i >= low; i--){
			sum += array[i];
			
			if(sum > leftSum){
				leftSum = sum;
				maxLeft = i;
			}
		}
		
		sum = 0;
		
		double rightSum = Double.NEGATIVE_INFINITY;
		int maxRight = -1;
		
		for(int j = mid + 1; j <= high; j++){
			sum += array[j];
			
			if(sum > rightSum){
				rightSum = sum;
				maxRight = j;
			}
		}
		
		Tuple<Integer,Integer,Double> result = new Tuple<>(maxLeft, maxRight, leftSum+rightSum);
		return result;
	}
}
import org.junit.Assert;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;


import org.junit.Test;

@RunWith(JUnit4.class)
public class Maximum_Subarray_test extends Maximum_Subarray{

	@Test
	public void test() {
		double[] testArray = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
		String correctResult = "(7,10,43.0)";
		String result = maxSubarray(testArray,0,testArray.length-1).toString();
		
		String errorMessage = "Error, correct result is (7,10,43.0), instead got " + result;
		
		Assert.assertEquals(errorMessage,correctResult,result);
		
		double[] testArray2 = {1,2,3,4,5};
		correctResult = "(0,4,15.0)";
		result = maxSubarray(testArray2,0,testArray2.length-1).toString();
		
		Assert.assertEquals(errorMessage,correctResult,result);
	}

}
public class Tuple<X,Y,Z> {
	private X x;
	private Y y;
	private Z z;
	
	public Tuple(X x, Y y, Z z){
		this.x = x;
		this.y = y;
		this.z = z;
	}
	
	public void setX(X x){
		this.x = x;
	}
	
	public void setY(Y y){
		this.y = y;
	}
	
	public void setZ(Z z){
		this.z = z;
	}
	
	public X getX(){
		return x;
	}
	
	public Y getY(){
		return y;
	}
	
	public Z getZ(){
		return z;
	}
	
	public String toString(){
		return "(" + x + "," + y + "," + z + ")";
	}

}