计蒜客 T1722 利润 （动态规划入门 C++）

计蒜客 T1722 利润

题目描述

奶牛们开始了新的生意，它们的主人约翰想知道它们到底能做得多好。这笔生意已经做了 N (1≤N≤100,000) 天，每天奶牛们都会记录下这一天的利润 Pi (−1000≤Pi≤1000)。

约翰想要找到奶牛们在连续的时间期间（至少一天）所获得的最大的总利润，请你写一个计算最大利润的程序来帮助他。

输入格式

第一行，一个整数 N，表示天数。

接下来 N 行，每行一个整数 Pi​。

输出格式

一个整数，表示最大的总利润。

样例输入

7 -3 4 9 -2 -5 8 -3

样例输出

14

问题分析

本问题和最大子数组问题相似，将每天的利润记为p[i]，求p[i]中连续利润和的最大值maxP。这种问题我们最简单的思路就是枚举，但枚举的时间复杂度不太好接受；如果使用动态规划，可以用枚举来找规律： 假设Pn[i]是以p[i]结尾的最大连续利润和，则有两种情况：

Pn[i-1] > 0，Pn[i] = Pn[i-1] + p[i]；Pn[i-1] < 0，Pn[i] = p[i]；

针对输入样例进行分析：

代码

#include <iostream> #include <algorithm> using namespace std; const int N = 100000; int p[N]; //每一天的利润 int dp_rec(int p[], int n){ int Pn[n]; //记录最优子解 Pn[0] = p[0]; int res = Pn[0]; for(int i=1; i<n; i++){ //寻找最优子解 if(Pn[i-1] < 0) Pn[i] = p[i]; //情况1 else Pn[i] = Pn[i-1] + p[i]; //情况2 } for(int i=1; i<n; i++){//在最优子解中寻找最优解 if(res <= Pn[i]) res = Pn[i]; } return res; } int main(){ int n,maxP; cin >> n; for(int i=0; i<n; i++) cin >> p[i]; maxP = dp_rec(p, n); cout << maxP; return 0; }