分治法は最大のサブセグメントとを求めます

タイトルの説明:
n個の整数(負の整数である可能性がある)からなるシーケンスa 1,a 2,...,an,このシーケンスの連続するサブセグメント和の最大値を求める.サブセグメントのすべての要素と負の整数の場合、その最大サブセグメントと0を定義します.
入力
最初の行には正の整数n(n<1000)があり、後にnの整数が付いており、絶対値は10000未満である.ファイルが終わるまで.
しゅつりょく
最大サブセグメントとを出力します.
サンプル入力

6 -2 11 -4 13 -5 -2
    
20

主な考え方:
全シーケンスの最大サブセグメントと3つのケースがあります.1)前段と同じです.2)後段と同じ.3)前後2段にまたがる.
分治の考え方を用いて,配列a[p:q]全体をまずa[p:(p+q)/2]とa[(p+q)/2+1:q]の2つの領域に分割するが,この2つの領域の最大サブセグメントはやはり分割する必要があるので,1つの要素しか残っていないまで分割し続け,その後,これらのサブセグメントの中から中心を見つけ,両側に最大のサブセグメントを探し始めることができる.一歩一歩上へ探し始め、各サブセグメントが探している最大サブセグメントは、上の3つの状況を比較して最大サブセグメントを得る必要があります.
一般思想を分治する:
分治法で問題を解く一般的な手順:
(1)分解し、解決すべき問題をいくつかの規模の小さい同類の問題に分ける.
(2)解を求め、サブ問題を十分に時間に分け、より簡単な方法で解決する.
(3)併合,原問題の要求に応じて,サブ問題の解を層毎に併合して原問題の解を構成する.

#include 
#include 
using namespace std;
int f(int a[],int low, int high)
{
	int mid;
	int sum = 0;//      
	int leftsum = 0;//         
	int rightsum = 0;//         
	int rs = 0;//               
	int ls = 0;//             
	int lefts = 0;//     mid         
	int rights = 0;//     mid         
	if (low == high)
	{
		if (a[low] > 0)
			sum = a[low];
		else 
			sum = 0;
	}
	if (low < high) {
		mid = (low + high)/2;
		leftsum = f(a, low, mid);//           
		rightsum = f(a, mid + 1, high);//           
		for (int i = mid ; i >= low; i--) {
			lefts += a[i];
			if (ls < lefts)
				ls = lefts;
		}
		for (int j = mid + 1; j <= high; j++) {
			rights += a[j];
			if (rs < rights)
				rs = rights;
		}
		sum = ls + rs;//sum               
	}
	if (sum < rightsum)
		sum = rightsum;//            
	if (sum < leftsum)
		sum = leftsum;//            
	return sum;
}
int main()
{
	int n;
	int num[1000];
	while (cin >> n)
	{
		memset(num, 0, sizeof(num));
		for (int i = 0; i < n; i++)
		{
			cin >> num[i];
		}
		cout << f(num, 0, n - 1) << endl;

	}
	return 0;
}

転送リンク:https://blog.csdn.net/zhong36060123/article/details/4381391(最大サブセグメントと詳細(N種類の解法のまとめ))