#include<iostream>
using namespace std;

/*
給定由n個整數（可能為負整數）組成的序列a1,a2,...,an，求該序列形如{ak和}i<=k<j的最大值
當所有整數均為負數的時候定義其最大子段和為0。依此定義，所求的最優值為
max{0,max(1<=i<=j<=n){ak和}i<=k<j.
例如，當(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)時最大子段和為11 + -4 + 13 = 20 
*/

/*
最大子段和的簡單求法
*/
/*
int MaxSum( int n, int *a, int &besti, int& bestj )
{
	int sum = 0;
	for( int i = 1; i <= n; ++i )
	{
		for( int j = i; j <= n; ++j )
		{
			int thissum = 0;
			for( int k = i; k <= j; ++k )
			{
				thissum += a[k];
			}
			//對于每一個i開始到j都求這個序列的和
			if ( thissum > sum )
			{
				sum = thissum;
				besti = i;
				bestj = j;
			}
		}
	}
	return sum;
}
*/
/*
利用已經計算的結果改進算法得到
*/
/*
int MaxSum( int n, int *a, int &besti, int& bestj )
{
	int sum = 0;
	for( int i = 1; i <= n; ++i )
	{
		int thissum = 0;
		for( int j = i; j <= n; ++j )
		{
			thissum += a[j];
			//利用已經計算好的thissum，避免每次都重復計算
			if ( thissum > sum )
			{
				sum = thissum;
				besti = i;
				bestj = j;
			}
		}
	}
	return sum;
}*/

/*
最大子段和問題的分治算法
針對最大子段問題和這個具體問題，本身的結構，我們可以從算法設計的策略上對上述O(n^2)
計算時間的算法進行進一步的改進。從問題的解的結構可以看出，它適合分治法求解：
如果將所給的序列a[1:n]分為長度相等的兩段a[1:n/2]和a[n/2 + 1：n]，分別求出這兩段的最大子段和
，則a[1:n]的最大子段和有三種情形：
（1）a[1:n]的最大子段和與a[1:n/2]的最大子段和相同
（2）a[1:n]的最大子段和與a[n/2:n]的最大子段和相同
（3）a[1:n]的最大子段和為{ak}i<=k<j，且1 <= i <= n/2, n/2 + 1 <= j <= n
（1）（2）兩種情形可以遞歸求得。情形（3），容易看出a[n/2]與a[n/2+1]在最優子序列中。因此
，我們可以在a[1:n/2]中計算出s1 = {1 <= i <= n/2}max{ak}{i <= k < n/2 },并在a[n/2+1:n]中計算
出s2 = {n/2 + 1 <= i <= n}max{ak}{n/2 + 1 <= k < n }則s1+s2即為（3）時的最優值
*/

int MaxSubSum( int *a, int left, int right )
{
	int sum = 0;
	if ( left == right )
	{
		sum = a[left] > 0 ? a[left]:0;
	}
	else
	{
		int center = ( left + right ) / 2;
		int leftsum = MaxSubSum( a, left, center );
		int rightsum = MaxSubSum( a, center + 1, right );

		int lefts = 0;
		int s = 0;
		for( int i = center; i >= left; --i )
		{
			lefts += a[i];
			if ( lefts > s )
			{

				s = lefts;
			}
		}

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

		sum = rs + s;
		if ( sum < leftsum )
		{
			sum = leftsum;
		}
		if ( sum < rightsum )
		{
			sum = rightsum;
		}
	}
	return sum;
}

int MaxSum( int n, int *a )
{
	return MaxSubSum( a, 1, n );
}


/*
最大子段和問題的動態規劃算法

在對上述的分治理算法的分析中，我們注意到，
若記b[j] = {從(1-j)中的下標開始到j的子段和中最大值}{1<=i<=j<=n}
也就是以a[j]為結尾的最大子段和
整體最大子段和為：
max{b[j]}{1<=j<=n}
因此，當b[j-1]>0時b[j] = b[j-1] + a[j]，否則b[j] = a[j]。由此
得到計算b[j]的動態規劃遞歸式：
b[j] = max{b[j-1] + a[j],a[j]},1<=j<=n
*/

/*
int MaxSum( int n, int *a, int &besti, int &bestj )
{
	int sum = 0;
	int b = 0;
	int flag = 0;
	for( int i = 1; i <= n; ++i )
	{
		if ( !flag )
		{
			besti = i;
			bestj = i;
			flag = 1;
		}

		if ( b > 0 )
		{
			b += a[i];
		}
		else
		{
			besti = i;
			bestj = i;
			b = a[i];
		}
		//calculate b[i]
		if ( b > sum )
		//record the max b[i] by variable sum
		{
			bestj = i;
			sum = b;
		}
	}

	return sum;
}*/

/*
最大子段和問題與動態規劃算法的推廣
（1）最大子矩陣和問題：給定一個m行n列的整數矩陣A，試求矩陣A的一個子矩陣
使各元素之和最大。
用二維數組a[1:m][1:n]表示給定的m行n列的整數矩陣。
子數組a[i1:i2][j1:j2]表示左上角
和右下角行列坐標分別為(i1,j1)和(i2,j2)的子矩陣。

注意到
max{1<=i1<=i2<=m}{1<=j1<=j2<=n}s(i1,i2,j1,j2) 
= max{1<=i1<=i2<=m}{ {1<=j1<=j2<=n}s(i1,i2,j1,j2) }
= max{1<=i1<=i2<=m}t(i1,i2)，

其中，t(i1,i2) = max{1<=j1<=j2<=n}s(i1,i2,j1,j2)
=max{1<=j1<=j2<=n}<j=j1..j2><i=t1..t2>a[i][j]
設b[j] = <i=i1...i2>a[i][j]，
則t(i1,i2) = max{1<=j1<=j2<=n}<j=j1...j2>b[j]

//先在同一行內，行范圍確定情況下，找出列的最大字段和轉換為一維的
//之后再求出行范圍的最大字段和，哪些行在一起的總和是最大的
//b[j]記錄的就是在行范圍確定下第J列的總和
//列方向的最大字段和就是求b[j]的最大字段和，如果b[j]的最大字段和求到，就能確定J的
范圍了。之后再求t[i][j]在行上的最大字段和，因為此時J已經確定
*/
int MaxSum2( int m, int n, int **a )
{
	int sum = 0;
	int *b = new int[n+1];
	for( int i = 1; i <= m; ++i )
	//1<=i1<=m
	{
		for( int k = 1; k <= n; ++k )
		{
			b[k] = 0;
		}

		for( int j = i; j <= m; ++j )
		//i<=i2<=m,每次開始都從i到m之間找到最大的行范圍
		{
			for( int k = 1; k <= n; ++k )
			{
				b[k] += a[j][k];
				//i1...i2
			}
			//j是行的增加來決定b數組的增長
			int max = MaxSum( n, b );
			//b[1]...b[n]的最大子段和
			if ( max > sum )
			{
				sum = max;
				//sum的值始終記錄的是一個最大的
			}
		}
	}
	return sum;
}

/*
最大m子段和問題：
給定由n個整數（可能為負數）組成的序列a1,a2,...,an,以及一個正整數m,
要求確定序列a1,a2,...,an的m個不相交子段
使得這m個子段的總和達到最大。

最大m子段和問題是最大子段和問題在子段個數上的推廣。
設b(i,j)表示數組a的前j項中i個子段和的最大值，且第i個子段含a[j](1<=i<=m,i<=j<=n)
則所求的最優值顯然為max(m<=j<=n)b(m,j)。
與最大子段和問題類似地
b(i,j) = max( b(i,j-1) + a[j], max{i-1<=t<j}b(i-1,t)+a[j]}
其中b(i,j-1)+a[j]項表示第i個子段含a[j-1]，
而max{i-1<=t<j}b(i-1,t)+a[j]表示第i個子段
僅含a[j]。初始時b(0,j) = 0,(1<=j<=n)
b(i,0) = 0(1<=i<=m)
*/

int MaxSumMore( int m, int n, int *a )
{
	if ( n < m || m < 1 )
	{
		return 0;
	}
	int **b = new int*[m+1];
	for( int i = 0; i <= m; ++i )
	{
		b[i] = new int[n+1];
	}
	for( i = 0; i <= m; ++i )
	{
		b[i][0] = 0;
	}
	for( int j = 1; j <= n; ++j )
	{
		b[0][j] = 0;
	}
	for( i = 1; i <= m; ++i )
	{
		for( int j = i; j <= n - m + i; ++j )
		//至少要留有n-(m-i)項，如果沒有，說明根本不能分成m段,b[i][j]是
		//包含a[j]在內的前i個子段的和
		{
			if ( j > i )
			{
				b[i][j] = b[i][j-1] + a[j];
				//先假設第I個子段包含a[j]
				for( int k = i - 1; k < j; ++k )
				{
					if ( b[i][j] < b[i-1][k] + a[j] )
					{
						b[i][j] = b[i-1][k] + a[j];
					}
					//從i-1到j之間找到最大的b[i-1][k],也就是包含i-1個子段和
					//的最大的一個
				}
			}
			else
			{
				b[i][j] = b[i-1][j-1] + a[j];
			}
		}
	}
	int sum = 0;
	for( j = m; j <= n; ++j )
	{
		if ( sum < b[m][j] )
		{
			sum = b[m][j];
		}
	}
	return sum;
}

/*
注意到上述算法中，
計算b[i][j]時只用到數組b的第i-1行和第i行的值。
因而算法中只要存儲數組b的當前行，不必存儲整個數組。
另一方面，max{i-1<=t<j}b(i-1,t)的值可以在計算第i-1行時，
預先保存起來。這樣一來，在計算第i行的值時不必重新計算，節省了計算時間和空間。
按此思想可對上述算法
做進一步的改進。
*/

int MaxSumMore1( int m, int n, int *a )
{
	if ( n < m || m < 1 )
	{
		return 0;
	}

	int *b = new int[n+1];
	//b[i]用來記錄前i項中最
	int *c = new int[n+1];
	b[0] = 0;
	c[1] = 0;
	for( int i = 1; i <= m; ++i )
	{
		b[i] = b[i-1] + a[i];
		//b[i]等同與b[i][i]
		c[i-1] = b[i];
		//相當前i項中前i-1個子段和的最大值
		int max = b[i];
		for( int j = i + 1; j <= i + n - m; ++j )
		{
			b[j] = b[j-1] > c[j-1] ? b[j-1] + a[j] : c[j-1] + a[j];
			//b[j]等同于b[i][j],前j項中前i個子段的最大和
			c[j-1] = max;
			//前j-1項中前i-1個子段的和
			if ( max < b[j] )
			{
				max = b[j];
			}
		}
		c[i+n-m] = max;
		//前i+n-m項中，前i個子段的最大和
	}

	int sum = 0;
	//b[j]中記錄的都是b[m][j]的值
	for( int j = m; j <= n; ++j )
	{
		if ( sum < b[j] )
		//b[j]中記錄了前j項數據中，m個最大子段和
		{
			sum = b[j];
		}
	}

	return sum;
}

int main()
{
	cout<<"the max sum of array: "<<endl;
	int n = 6;
	int *a = new int[n+1];
	a[0] = 0;
	a[1] = -2;
	a[2] = 11;
	a[3] = -4;
	a[4] = 13;
	a[5] = -5;
	a[6] = -2;
	int besti,bestj;
	//int sum = MaxSum( n, a, besti, bestj );
	//int sum = MaxSum( n, a );
	int sum = MaxSumMore1( 3, 6, a );
	cout<<besti<<endl;
	cout<<bestj<<endl;
	cout<<sum<<endl;
	
	//MaxSum( int m, int n, int *a );
	return 0;
}