题解

#include <iostream>
using namespace std;
int maxSum(int arr[], int left, int right){
	if(left == right){
		if( arr[left] < 0 ){
			return 0;
		}else{
			return arr[left];
		}
	}else{
		int mid = ( left + right ) / 2;
		int leftMax = maxSum(arr, left, mid);
		int rightMax = maxSum(arr, mid+1, right);
		int maxLeftCross = 0;
		int maxLeftCrossTmp = 0;
		for(int i=mid; i>=left; i--){
			maxLeftCrossTmp += arr[i];
			if(maxLeftCrossTmp > maxLeftCross){
				maxLeftCross = maxLeftCrossTmp;
			}
		}
		int maxRightCross = 0;
		int maxRightCrossTmp = 0;
		for(int i=mid+1; i<=right; i++){
			maxRightCrossTmp += arr[i];
			if(maxRightCross < maxRightCrossTmp){
				maxRightCross = maxRightCrossTmp;
			}
		}
		int maxCross = maxLeftCross + maxRightCross;
		return max(leftMax, max(rightMax, maxCross));
	}
}

int main(){
	int n;
	cin >> n;
	int arr[100];
	for(int i=0; i<n; i++)
		cin >> arr[i];
	cout << maxSum(arr, 0, n-1) << endl;
	return 0;
}