学步园

4.1 最大子数组问题

#include <common.h>

//FIND-MAX-CROSSING-SUBARRAY
static void find_max_crossing_subarray(
	__in const int *A,
	__in int low,
	__in int mid,
	__in int high,
	__out int *max_left_index,
	__out int *max_right_index,
	__out int *max_sum)
{
	int left_sum = INT_MIN, right_sum = INT_MIN;
	int sum = 0;
	int i, l, r;

	for (i= mid; i >= low; --i) {
		sum = sum + A[i];
		if (sum > left_sum) {
			left_sum = sum;
			l = i;
		}
	}

	sum = 0;
	for (i = mid + 1; i <= high; ++i) {
		sum = sum + A[i];
		if (sum > right_sum) {
			right_sum = sum;
			r = i;
		}
	}

	*max_left_index = l;
	*max_right_index = r;
	*max_sum = left_sum + right_sum;

	TRACE("%s: in (%d, %d, %d) out (%d, %d, %d)\n",
		__FUNCTION__,
		low, mid, high,
		*max_left_index,
		*max_right_index,
		*max_sum);
}

//FIND-MAXIMUM-SUBARRAY
static void find_max_subarray(
	__in const int *A,
	__in int low,
	__in int high,
	__out int *max_left_index,
	__out int *max_right_index,
	__out int *max_sum
	)
{
	int mid = 0;
	int l_l, l_r, l_s;	//left_left_index; ..
	int r_l, r_r, r_s;	//right_left_index; ..
	int c_l, c_r, c_s;	//cross_left_index; ..

	if (high == low) {
		*max_left_index = low;
		*max_right_index = high;
		*max_sum = A[low];
		goto l_exit;
	}

	mid = (low + high)/2;

	find_max_subarray(
		A,low, mid,
		&l_l, &l_r, &l_s);

	find_max_subarray(
		A, mid+1, high,
		&r_l, &r_r, &r_s);

	find_max_crossing_subarray(
		A, low, mid, high,
		&c_l, &c_r, &c_s);

	if (c_s >= l_s && c_s >= r_s) {
		*max_left_index = c_l;
		*max_right_index = c_r;
		*max_sum = c_s;
		goto l_exit;
	}

	if (l_s >= r_s) {
		*max_left_index = l_l;
		*max_right_index = l_r;
		*max_sum = l_s;
		goto l_exit;
	}

	*max_left_index = r_l;
	*max_right_index = r_r;
	*max_sum = r_s;

l_exit:
	TRACE("%s: in (%d, %d) out (%d, %d, %d)\n",
		__FUNCTION__,
		low, high,
		*max_left_index,
		*max_right_index,
		*max_sum);
}

void func_4_1(void)
{
	const int A[] = {
		13, -3, -25, 20, -3, -16, -23, 18,
		20, -7, 12, -5, -22, 15, -4, 7	
	};

	int l, r, sum;

	find_max_subarray(
		A, 0, sizeof(A)/sizeof(int) -1,
		&l, &r, &sum);

	TRACE("%s: (%d, %d, %d)\n",
		__FUNCTION__,
		l, r, sum);
}

输出结果:

        《算法导论》
=========第四章 分治策略=========
find_max_subarray: in (0, 0) out (0, 0, 13)
find_max_subarray: in (1, 1) out (1, 1, -3)
find_max_crossing_subarray: in (0, 0, 1) out (0, 1, 10)
find_max_subarray: in (0, 1) out (0, 0, 13)
find_max_subarray: in (2, 2) out (2, 2, -25)
find_max_subarray: in (3, 3) out (3, 3, 20)
find_max_crossing_subarray: in (2, 2, 3) out (2, 3, -5)
find_max_subarray: in (2, 3) out (3, 3, 20)
find_max_crossing_subarray: in (0, 1, 3) out (0, 3, 5)
find_max_subarray: in (0, 3) out (3, 3, 20)
find_max_subarray: in (4, 4) out (4, 4, -3)
find_max_subarray: in (5, 5) out (5, 5, -16)
find_max_crossing_subarray: in (4, 4, 5) out (4, 5, -19)
find_max_subarray: in (4, 5) out (4, 4, -3)
find_max_subarray: in (6, 6) out (6, 6, -23)
find_max_subarray: in (7, 7) out (7, 7, 18)
find_max_crossing_subarray: in (6, 6, 7) out (6, 7, -5)
find_max_subarray: in (6, 7) out (7, 7, 18)
find_max_crossing_subarray: in (4, 5, 7) out (5, 7, -21)
find_max_subarray: in (4, 7) out (7, 7, 18)
find_max_crossing_subarray: in (0, 3, 7) out (3, 4, 17)
find_max_subarray: in (0, 7) out (3, 3, 20)
find_max_subarray: in (8, 8) out (8, 8, 20)
find_max_subarray: in (9, 9) out (9, 9, -7)
find_max_crossing_subarray: in (8, 8, 9) out (8, 9, 13)
find_max_subarray: in (8, 9) out (8, 8, 20)
find_max_subarray: in (10, 10) out (10, 10, 12)
find_max_subarray: in (11, 11) out (11, 11, -5)
find_max_crossing_subarray: in (10, 10, 11) out (10, 11, 7)
find_max_subarray: in (10, 11) out (10, 10, 12)
find_max_crossing_subarray: in (8, 9, 11) out (8, 10, 25)
find_max_subarray: in (8, 11) out (8, 10, 25)
find_max_subarray: in (12, 12) out (12, 12, -22)
find_max_subarray: in (13, 13) out (13, 13, 15)
find_max_crossing_subarray: in (12, 12, 13) out (12, 13, -7)
find_max_subarray: in (12, 13) out (13, 13, 15)
find_max_subarray: in (14, 14) out (14, 14, -4)
find_max_subarray: in (15, 15) out (15, 15, 7)
find_max_crossing_subarray: in (14, 14, 15) out (14, 15, 3)
find_max_subarray: in (14, 15) out (15, 15, 7)
find_max_crossing_subarray: in (12, 13, 15) out (13, 15, 18)
find_max_subarray: in (12, 15) out (13, 15, 18)
find_max_crossing_subarray: in (8, 11, 15) out (8, 15, 16)
find_max_subarray: in (8, 15) out (8, 10, 25)
find_max_crossing_subarray: in (0, 7, 15) out (7, 10, 43)
find_max_subarray: in (0, 15) out (7, 10, 43)
func_4_1: (7, 10, 43)