The maximum-subarray problem

Problem Description

The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Example

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

Features

The input array should contains negative number(s), otherwise the output will be the whole input array, which is meaningless.

Algorithm 1: Brute-Force Solution Θ(n2)

Java Implementation

public Map<String, Integer> FindMaximumSubarrayBruteForce(int[] A){
	Map<String, Integer> resultMap = new HashMap<String, Integer>();
	int max = -Integer.MAX_VALUE;
	int low = 0;
	int high = 0;
	for(int i=0; i<A.length; i++){
		int tempSum = 0;
		for(int j=i; j<A.length; j++){
			tempSum += A[j];
			if(tempSum > max){
				max = tempSum;
				low = i;
				high = j;
			}
		}
	}
	resultMap.put("low", low);
	resultMap.put("high", high);
	resultMap.put("maxSum", max);
	return resultMap;
}

Output: {high=6, low=3, maxSum=6}

Algorithm 2: Divide and Conquer with Θ(nlgn)

Pseudocode

FIND-MAXIMUM-SUBARRAY(A, low, high)
    if high == low then
        return (low, high, A[low])               // base case: only one element
    else
        mid = (low + high) / 2
        (left-low, left-high, left-sum)= FIND-MAXIMUM-SUBARRAY(A, low, mid)
        (right-low, right-high, right-sum)= FIND-MAXIMUM-SUBARRAY(A, mid+1, high)
        (cross-low, cross-high, cross-sum)= FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
        if left-sum >= right-sum and left-sum >=cross-sum then
                return (left-sum, left-low, left-high)
        elseif right-sum >= left-sum and rigth-sum >=cross-sum then
                return (right-sum, right-low, right-high)
        else
                return (cross-sum, cross-low, cross-high)
        endif
     endif
end FIND-MAXIMUM-SUBARRAY
FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
    left-sum = -infity
    sum = 0
    for i = mid downto low
        sum = sum + A[i]
        if sum > left-sum
            left-sum = sum
            max-left = i
    right-sum = -infity
    sum = 0
    for i = mid + 1 to high
        sum = sum + A[i]
        if sum > right-sum
            right-sum = sum
            max-righ = i
    return (max-left, max-right, left-sum+right-sum)
end FIND-MAX-CROSSING-SUBARRAY

 

Java Implementation

package com.chengkaiblog.algorithm.MaxiumSubArray;

import java.util.HashMap;
import java.util.Map;

public class MaxiumSubArray {

	public Map<String, Integer> FindMaximumSubarray(int[] A, int low, int high){
		Map<String, Integer> map = new HashMap<String, Integer>();
		if(low == high){
			map.put("low", low);
			map.put("high", high);
			map.put("maxSum", A[low]);
		}
		else{
			Map<String, Integer> leftMap = new HashMap<String, Integer>();
			Map<String, Integer> rightMap = new HashMap<String, Integer>();
			Map<String, Integer> midMap = new HashMap<String, Integer>();
			int mid = (low + high) / 2;
			leftMap = FindMaximumSubarray(A, low, mid);
			rightMap = FindMaximumSubarray(A, mid + 1, high);
			midMap = FindMaxCrossingSubbarray(A, low, mid, high);
			if(leftMap.get("maxSum")>rightMap.get("maxSum") && leftMap.get("maxSum")>midMap.get("maxSum")){
				return leftMap;
			}
			else if(rightMap.get("maxSum")>leftMap.get("maxSum") && rightMap.get("maxSum")>midMap.get("maxSum")){
				return rightMap;
			}
			else{
				return midMap;
			}
		}
		return map;
	}
	
	
	// at least two elements
	private Map<String, Integer> FindMaxCrossingSubbarray(int[] A, int low, int mid, int high){
		Map<String, Integer> map = new HashMap<String, Integer>();
		int leftMax = -Integer.MAX_VALUE;
		int rightMax = -Integer.MAX_VALUE;
		int leftLow = mid;
		int rightHigh = mid + 1;
		// scan left subarray
		int tempMax = 0;
		for(int i=mid; i>=low; i--){
			tempMax += A[i];
			if(tempMax > leftMax){
				leftMax = tempMax;
				leftLow = i;
			}
		}
		
		// scan right subarray
		tempMax = 0;
		for(int i=mid+1; i<=high; i++){
			tempMax += A[i];
			if(tempMax > rightMax){
				rightMax = tempMax;
				rightHigh = i;
			}
		}
		map.put("low", leftLow);
        map.put("high", rightHigh);
        map.put("maxSum", leftMax + rightMax);
		return map;
	}
}
MaxiumSubArray msa = new MaxiumSubArray();
//int[] A = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
int[] A= {-2, 1, -3, 4, -1, 2, 1, -5, 4};
Map<String, Integer> result = new HashMap<String, Integer>();
result = msa.FindMaximumSubarray(A, 0, A.length - 1);
System.out.println(result);

Output: {high=6, low=3, maxSum=6}

Algorithm 3: Dynamic Programming with Θ(n)

Java Implementation

public Map<String, Integer> FindMaximumSubarrayDP(int[] A){
	Map<String, Integer> resultMap = new HashMap<String, Integer>();
	int[] solution = new int[A.length+1];
	solution[0] = 0;
	for(int i=0; i < A.length; i++){
		solution[i+1] = Math.max(solution[i] + A[i], A[i]);
	}
	// find max value in solution array
	int maxSolution = solution[0];
	int maxIndex = 0;
	for(int i=1; i <= A.length; i++){
		if(solution[i] > maxSolution){
			maxSolution = solution[i];
			maxIndex = i;
		}
	}
	// find the start index and end index of the max subarray
	int sum = 0;
	resultMap.put("high", maxIndex-1);
	resultMap.put("maxSum", maxSolution);
	for(int i=maxIndex-1; i>=0; i--){
		sum += A[i];
		if(sum == maxSolution){
			resultMap.put("low", i);
			break;
		}
	}
	return resultMap;
}
MaxiumSubArray msa = new MaxiumSubArray();
//int[] A = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
int[] A= {-2, 1, -3, 4, -1, 2, 1, -5, 4};
Map<String, Integer> result = new HashMap<String, Integer>();
result = msa.FindMaximumSubarrayDP(A);
System.out.println(result);

Output: {high=6, low=3, maxSum=6}

性质

以数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]为例,讨论最大子数组的性质。

如果a[1..j]已经得到了其最大子数组,那么a[1..j+1]最大子数组只能是两种情况

  1. a[1..j+1]的最大子数组就是a[1..j];
  2. a[1..j+1]的最大子数组是a[i..j+1],1<=i<=j;

那么,如何求得所谓的2中的a[i..j+1]呢?

首先需要承认这样的事实,如果一个数组a[p..r]求和得到负值,那么数组a[p..r+1]的最大子数组肯定不会是a[p..r+1],因为a[p..r]+a[r+1]<a[r+1]
在以上程序中,我们用solution存储所谓的a[p..r]的和,只要a[p..r]的求和是负值,那么从下一个a[r+1]值开始,solution重新从零开始求和。我们一次遍历后,就能得到最大的和。接下来,我们阐述划分块的五个性质以证明该算法是有效的。

对于所有数组元素,这样的元素对数组进行划分,如果加上该元素之前temp>0temp+a[i]<0,那么该元素a[i]是一个边界,这样,数组会形成好多段,每段结束元素都满足temp>0temp+a[i]<0.所以我们能得到多个划分块a[p..q],每个划分块的和是负值,划分块有这样的性质,

性质一

对任意p<=i<q,显然,sum(a[p..i])>=0sum(a[p..q])<0;

性质一是由划分块的性质得到的,无需证明。

性质二

每个划分块中,当划分块包含2个及2个以上的元素时,划分块最左端的元素必大于0,划分块右端的元素必小于0。当划分块包含1个元素时,该元素必小于0。

性质二也是由划分块的性质得到的,无需证明。

性质三

以划分块最右端元素作为结尾的划分块内子数组的和必小于0。

证明:

假设子数组数组a[p...q]为其中一个划分块。

p<=i<q时,那么必有sum(a[p...i])>=0,因为如果sum(a[p...i])<0,那么a[p...q]不会被划分为一个划分块,而会被划为多个划分块。又因为sum(a[p...q])=sum(a[p...i])+sum(a[i+1...q])<0,所以sum(a[i+1...q])<0

i=q时,由性质二可得,sum(a[q])<0

得证。

性质四

最大子数组一定是以划分块的首元素为起始的数组。

证明:

对于某个划分块a[p...q],假设存在a[i...j],其中p<i<=j<q,那么根据证明性质二过程中的结论,可得sum(a[p...i-1])>0,那么a[p..i-1]+a[i..j]>=a[i..j]必定成立。因此最大子数组一定是以划分块的首元素为起始的数组。

得证。

性质五

最大子数组一定在划分块之内,且不包含划分块的最后一个元素。

证明:

利用反证法。假设最大子数组可以横跨多个划分块。根据性质二,最大子数组的起始元素就是划分块的起始元素。根据性质三,最大子数组的和加上前一个划分块的后半部分,其和一定小于最大子数组的和。因此,最大子数组不可能左跨两个划分块。又根据性质一,划分块的最后一个元素是负数,因此,最大子数组一定不包含划分块的最后一个元素,即最大子数组不可能右跨两个划分块。

综上所述,最大子数组一定在划分块之内,且不包含划分块的最后一个元素。

得证。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

5 × 5 =

18 + = 28