蒟蒻提高计划NO.1

代码:

DP(动态规划)部分:

int DP(){//动态规划函数 
	int i;
	for(i=2;i<=n;i++){//i=2是为了数组不越界 
		dp[i]=max(dp[i-1]+a[i],a[i]);//动态转移方程 
		if(maxs<dp[i]){//判断大小 
			maxs=dp[i];
		}
	}
	return maxs;//返回最大值 
}

main部分:

cin>>n;//输入元素个数 
	for(i=1;i<=n;i++){//输入a数组内容 
		cin>>a[i];
	}
	dp[1]=a[1];//将dp[1]附为a[1] 
	cout<<DP();//执行并输出DP函数的结果

总结:

难点：动态转移方程

考点：动态规划(DP)

综合指数：▲▲▲◭

使用动态规划即可

动态转移方程是

$f[i] = max(f[i - 1] + a[i], a[i])$

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int f[1005], n, a[1005];
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = -1000005;
    f[1] = a[1];
    for (int i = 2; i <= n; i++)
    {
        f[i] = max(f[i - 1] + a[i], a[i]);
        ans = max(f[i], ans);
    }
    cout << ans << endl;
    return 0;
}

• 刷信奥赛CSP-J 难度1：题目3
• 【基础】最大部分和（连续部分和）
• 这是经典动态规划“四大天王”之一，要重视！

1. 动态规划，那肯定要有个 f 数组啊，范围就定105（100+5）并且要有个 ans 记录最大部分
2. 之后定义 n、a[i]，进行输入处理
3. 紧接着在草稿纸上列出转台转移方程：f[i] 为 f[i - 1] 加上 a[i] 和 a[i] 的最大值，f[i]则表示以a[i]结尾的最大子序列和`
4. 最后从 i 循环到 n。注意！：要每一次更新变量！
5. 最后见代码吧~（UP整数字了，珍惜吧，时间很宝贵滴！）

#include <bits/stdc++.h>
using namespace std;
int n, a[105];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    //求和最大子序列
    //编写动态规划，f[i]表示以a[i]结尾的最大子序列和
    int f[10005];
    int ans = 0;
    //ans 存储最终数值
    for (int i = 1; i <= n; i++)
    {
        //状态转移方程：f[i]为f[i - 1]加上a[i]和a[i]的最大值
        f[i] = max(f[i - 1] + a[i], a[i]); 
        ans = max(ans, f[i]);
        //更新最终值
    }
    cout << ans << endl;
    return 0;
}

动态规划

第一步：f[1]初始值--a[1]

第二步：转移方程

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

answer变量记录一下

#include <bits/stdc++.h>
using namespace std;
int a[110],f[110],n,answer=INT_MIN;
int main(){
    std::cin>>n;
    for (int i=1;i<=n;i++)std::cin>>a[i];
    f[1]=a[1];
    for (int i=2;i<=n;i++){
        f[i]=max(f[i-1]+a[i],a[i]);
        answer=max(answer,f[i]);
    }
    cout<<answer;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,a[105],ans=-114514,f[105];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); // 输入加速
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    // 状态转移方程
    // f[i] = max(f[i - 1] + a[i], a[i]);
    // f[i]记录以a[i]为子序列末端的最大连续和
    for(int i = 1; i <= n; i++) {
        f[i]=max(f[i-1]+a[i],a[i]);
        ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;
}

求的是连续的部分和最大，不是最大子序列和。
思路：设f[i]为到a[i]为止的连续部分和
f[1]显然就是a[1]
从2开始，如果f[i-1]是大于0的，那么f[i]显然就是f[i-1]+a[i]
如果小于等于0，那么f[i]就是a[i]自己
注意f[n]并不一定就是最大的值，需要求出最大ans，
ans初始值设成最小值大于-10000即可
#include<bits/stdc++.h>
using namespace std;
int n,a[105],f[105],ans=-10005;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	f[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		if(f[i-1]>0)
		{
			f[i]=f[i-1]+a[i];
		}
		else
		{
			f[i]=a[i];
		}
		ans=max(f[i],ans);
	}
	cout<<ans;
	return 0;
}

这题其实很简单，只要使用一个DP就可以解决。观察题干，设dp[i]表示以第i个位置的数结尾的最大连续部分和。不难发现，dp[1] = -2，dp[2] = 11，dp[3] = 25… …其状态转移方程为：

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

于是根据这个方程，我们就可以解题啦~ 上AC代码

 int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    
    dp[1] = -2;
    int ans = -2;
    
    for (int i = 2;i <= n;i++)
    {
        //dp[i]的两种情况:1、选a[i]:dp[i - 1] + a[i] 2、不选dp[i - 1]得a[i],取较大值
        dp[i] = max(a[i],dp[i - 1] + a[i]);
        ans = max(ans,dp[i]);
    }
    
    cout << ans << endl;

此题使用动态规划

#include <iostream>
using namespace std;
int n, a[100005], f[100005], ans = -1000000000;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        f[i] = max( a[i] , f[i - 1] + a[i]);
        ans = max(ans, f[i]);
    }
    cout << ans;
    return 0;
}

for(int i=1;i<=n;i++)//i是起点
{
   for(int j=i;j<=n;j++)//j是终点
   {
       if(arr[j]-arr[i-1]>ans) ans=arr[j]-arr[i-1];//求最大和
   }
}//<-核心代码^^^^^^^^^^^^^^^^^^^^^

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。