学步园

/*
 * MaxSumSubArray.cpp
 *
 *  Created on: 2012-6-20
 *      Author: jiyiqin
 *
 *  给定一个包含正数，负数，0的数组，求一个连续的子数组，使得其和最大
 */
#include <iostream>
using namespace std;

#define MIN_INT -10000
class MaxSumOfSubArray{
public:

	/**
	 * 二重循环查找最大和子数组，依次以a[i]为起点，
	 * 求解sum[i,j],更新当前最大和的值
	 * 注意数组全是负数的情况
	 * */
	static int m1_subArray(int a[], int size)
	{
		int max_sum = MIN_INT;					//max赋值一次
		if(a == NULL || size <=0) return -1;	//输入是否合法判断

		for(int i=0;i<size;i++)
		{
			int sum = 0;
			for(int j=i;j<size;j++){
				sum += a[j];
				if(sum > max_sum) max_sum = sum;	//更新max
			}
		}
		cout<<"max_sum:"<<max_sum<<endl;
		return 1;
	}

	/**
	 * 线性时间完成：
	 * 记录当前max，逐个累加
	 * 如果和sum变成负，丢弃(更新起点)。
	 * 如果sum > max，更新max。
	 * 注意数组全部是负数的时候，"负数和"也拥有和当前最大和比较的权利
	 * */
	static int m2_subArray(int a[], int size)
	{
		int max_sum = MIN_INT;					//最大和初值为最小数字
		int sum = 0;
		if(a == NULL || size <=0) return -1;	//输入是否合法判断

		for(int i=0;i<size;i++)
		{
			sum += a[i];
			if(sum > max_sum) max_sum = sum;	//更新max
			if(sum <= 0) sum = 0;				//重新开始计算和
		}
		cout<<"max_sum:"<<max_sum<<endl;
		return 1;
	}

	/**
	 * 动态规划方法：
	 * 很明显求解最大子数组和的问题有子结构，并且满足“无后效性”。
	 * 即问题可以被划分为多个阶段，未来阶段状态f(i+1)的求解仅仅与
	 * 当前状态f(i)通过状态转移方程得到，而与过去的历史状态无关。
	 * 我们设sum(i)为以a[i]结尾的最大子数组和.
	 *
	 * 如果sum(i-1) =< 0:
	 * 		很明显我们不应当将其简单抛弃，因为我们还要考虑数组a全部都是负数的情况，
	 * 		所以我们仍然将其与a[i]比较，所以sum(i) = max{sum(i-1), a[i]};
	 * 如果sum(i-1) > 0:
	 * 		因为sum(i-1)是以a[i-1]结尾的，所以很明显sum(i) = sum(i-1)+a[i];
	 * 所以我们得到状态转移方程如下：
	 * sum(i) =
	 * 		sum(i-1)+a[i];			sum(i-1) > 0
	 * 		max{sum(i-1), a[i]};	sum(i-1) <= 0
	 * */
	static int m3_subArray(int a[], int size)
	{
		int *sum = new int[size];
		int max_sum = MIN_INT;
	
		if(a == NULL || size <= 0) return -1;	//判断输入是否合法
		for(int k=0;k<size;k++) sum[k] = 0;		//初始化sum数组

		//顺着i自底向上求解
		sum[0] = a[0];
		for(int i=1;i<size;i++)
		{
			if(sum[i-1] > 0) sum[i] = sum[i-1]+a[i];
			else sum[i] = sum[i-1]>a[i]?sum[i-1]:a[i];
			
			//更新max_sum
			if(sum[i] > max_sum) max_sum = sum[i];
		}
		
		//输出结果
		cout<<"max_sum:"<<max_sum<<endl;
		for(int j=0;j<size;j++)
			cout<<sum[j]<<" ";
		cout<<endl;
		return 1;
	}

	static void test(){
		int a[10] = {-1,2,-5,2,-1,-13,15,-2,8,-1};
		for(int i=0;i<10;i++){
			cout<<a[i]<<" ";
		}
		cout<<endl;

		m1_subArray(a, 10);	//方法1
		m2_subArray(a, 10);	//方法2
		m3_subArray(a, 10);	//方法3
	}
};

int main(){
	MaxSumOfSubArray::test();
	return 0;
}