目录

简单版

题目

code

本题

code

简单版

先要会做这道题

题目

P1115 最大子段和https://www.luogu.com.cn/problem/P1115

这道题其实是动态规划,dp,但是很水。

code

#include<bits/stdc++.h>

using namespace std;

int n, j, sum, maxx;

int main() {

	cin >> n >> maxx;

	sum = maxx;

	for (int i = 2; i <= n; i++) {

		cin >> j;

		if (sum < 0) sum = 0;

		sum += j;

		maxx = max(maxx, sum);

	}

	cout << maxx << endl;

	return 0;

}

本题

再看这道题目，也不是很难。

详见代码。

code

#include <bits/stdc++.h>

using namespace std;

const int N = 1000005;

long long a[N];

long long w[N];

long long q[N];

long long f[N];

long long n;

long long mod;

long long maxx;

int main() {

	cin >> n >> mod;

	for (int i = 1; i <= n; i++) cin >> a[i];

	f[1] = w[1] = q[1] = a[1];

	maxx = a[1];

	for (int i = 2; i <= n; i++) {//i 从 2 开始

		w[i] = max(w[i - 1] + a[i], a[i]);

		//         接上一个  自己单独一个

		q[i] = max(q[i - 1], w[i]);

	}

	f[2] = f[1] + a[1];

	maxx = max(maxx, f[2]);

	for (int i = 3; i <= n; i++) {

		f[i] = max(f[i - 1], q[i - 1] + f[i - 1]);

		//上一个人的分数和上一个人自己的特征值加分数

		maxx = max(maxx, f[i]);

		//更新最大值

	}

	cout << maxx % mod << endl;

	return 0;

}

/*

*  w:以i为结尾的最长连续子段和

*  q:1~i中的最长连续子段和（特征值）

*  maxx:当前前i个w[i]的最大值

*/

P1982 [NOIP2013 普及组] 小朋友的数字 题解的相关教程结束。