程序设计:装修效果(2012年北京市CSP-S原题)

小明在美术课上给马上要过生日的妈妈做了张贺卡，为了装饰这张贺卡，小明买了一条彩带，但是彩带上并不是所有颜色小明都喜欢，于是小明决定裁剪这条彩带，以取得最好的装饰效果。

现已知彩带由 n 种不同的颜色顺次相接而成，而每种颜色的装饰效果用一个整数表示（包括正整数，0，或负整数），从左到右依次为 ，小明可以从中裁剪出连续的一段用来装饰贺卡，而装饰效果就是这一段上各个颜色装饰效果的总和，小明需要选取装饰效果最好的一段颜色来制作贺卡（取该段颜色数值之和的最大值）当然，如果所有颜色的装饰效果都只能起到负面的作用（即 ），小明也可以放弃用彩带来装饰贺卡（获得的装饰效果为 0）。

输入数据包括两行：

第一行是一个整数 n，表示彩带上颜色的个数；

第二行有 n 个整数，它们依次为a1,a2,a3......an(1 <= n <= 1000)

输出数据只有一个整数，表示贺卡最多能获得多少装饰效果。

5
-1 2 -1 2 -1

3

使用一个循环嵌套,

需要注意只有一种颜色的情况,

在 sum += a[j] 之前需要进行一次大小比较，来匹配只有一种颜色的情况.

#include
using namespace std;
int n,m,a[1005];
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        int sum = a[i];
    	for(int j = i + 1; j <= n; j++){
            m = max(sum, m);
            sum += a[j];
            m = max(sum, m);
        }
    }
    cout << m << endl;
    return 0;
}