文章

11

粉丝

20

获赞

4

访问

5.3k

头像
DP空间优化解法O(1),内存140kb
P1664 中南大学机试题
发布于2023年8月5日 13:00
阅读数 326

#include<cstdio>
int main() {
	int a, dp, maxT, left, right, leftmp, n;//不要随便定义在全局变量区,吃了很大的亏
	while (scanf("%d", &n) != EOF) {
		maxT = dp = left = right = 0;//初始化很重要!!!
		for (int i = 0; i < n; i++) {
			scanf("%d", &a);
			if (dp > 0) dp += a; //dp状态为正可以继续加
			else if (a > 0) {
				leftmp = i; dp = a;//leftmp记录下当前正数的位置
			}
			if (dp > maxT) {
				maxT = dp; right = i; left = leftmp;//这里就体现了leftmp的作用
			}
		}
		printf("%d %d %d\n", maxT, left, right);
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发