↓Skip to main content
  1. Posts/

CodeForces-1359D Yet Another Yet Another Task

·1 min·
Table of Contents

CodeForces-1359D Yet Another Yet Another Task #

题目大意 #

给定长度为 $n$ 的数组 $a$ (其中 $-30\leq a_i\leq 30$) . 设 $b$ 是 $a$ 的一个非空连续子数组, 求 $sum(b) - max(b) $ 的最大值.

Solution 1 #

寻找子段和减去子段最大值的最大值, 当子段最大值固定为 $m$ 时, 问题转化为寻找一个有约束的最大子段和, 这个约束就是元素值不能超过 $m$ . 同样运用贪心算法, 在 $sum < 0$ 的情况之外, 当 $a[i] > m$ 时同样将 $sum$ 重置为 $0$ . 代码如下:

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	int a[n];
	for (int &v: a) {
		cin >> v;
	}
	int ans = 0, sum = 0;
	for (int i = 1; i <= 30; i++) { 
		sum = 0;
		for (int v: a) {
			if (v > i) {
				sum = 0;
			}
			else {
				sum += v;
				if (sum < 0) {
					sum = 0;
				}
				else {
					ans = max(ans, sum - i);
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}