最大サブセグメント和(二)

最大サブセグメントと問題
 
解法二:分治法
アルゴリズム解析:
最大サブセグメントと3つの場所で表示される可能性があります.1)入力データの左半分2)全体が右半分に現れる.
3)入力データの中央部を越えて左右の2つの部分のうちの1つ前に位置する場合を再帰的に解くことができ,3つ目の場合の最大和は,前半の最大和(前半の最後の要素を含む)および後半の最大和(後半の最初の要素を含む)を求めることによって得られ,前後の2つの部分と加算される.3つの部分のうちの最大は、最大サブセグメント和である.
例:
前半後半
4  -3  5  -2    -1  2  6  -2
ここで、前半の最大サブセグメント和は6(A 1~A 3)であり、後半の最大サブセグメント和は8(A 6~A 7)である.
前半部はその最後の要素の最大和4(A 1~A 4)を含み、後半部はその最初の要素の最大和7(A 5~A 7)を含み、
この2つの部分にまたがる最大和は4+7=11である.
したがって、シーケンスの最大フィールド和は11である
 
アルゴリズムは以下のように実現される.

/*
 * description:      
 *     
 *             。
 * 1)             
 * 2)        。
 * 3)                     
 *            ，                       (             )
 *           (            )   ，        。
 *         ，       .
 * auther: cm
 * date: 2010/11/20
 */
public class MaxSubSumRec 
{
	private static int maxSumRec(int[] a, int left, int right)
	{
		if (left == right)
		{
			if (a[left] > 0)
			{
				return a[left];
			}
			else
			{
				return 0;
			}
		}

		int center = (left + right) / 2;
		int maxLeftSum = maxSumRec(a, left, center);
		int maxRightSum = maxSumRec(a, center + 1, right);

		int maxLeftBorderSum = 0;
		int leftBorderSum = 0;
		for (int i = center; i >= left; i--)
		{
			leftBorderSum += a[i];
			if (leftBorderSum > maxLeftBorderSum)
			{
				maxLeftBorderSum = leftBorderSum;
			}
		}

		int maxRightBorderSum = 0;
		int rightBorderSum = 0;
		for (int i = center + 1; i <= right; i++)
		{
			rightBorderSum += a[i];
			if (rightBorderSum > maxRightBorderSum)
			{
				maxRightBorderSum = rightBorderSum;
			}
		}

		return max(maxLeftSum, maxRightSum, maxRightBorderSum + maxLeftBorderSum);
	}

	//    
	public static int maxSubSum(int[] a)
	{
		return maxSumRec(a, 0, a.length - 1);
	}

	//        
	private static int max(int a, int b, int c)
	{
		int max = a > b ? a : b;
		max = c > max ? c : max;

		return max;
	}

	public static void main(String[] args) 
	{
		int[] a = {-2, 11, -4, 13, -5, -2};
		System.out.println(MaxSubSumRec.maxSubSum(a));
	}
}