先来问题叙述，
给定一个数列，求一个子列，此子列和为本数列和最大的子列
例如：1，2，3，-3
和最大子列为1，2，3
和为6
之所以不对问题进行大篇幅具体描述，因为这里主要进行算法方法学习
解决问题不过应用罢了
OK
下面我们来分析问题
当然你可以用最笨的方法，不过那太过复杂了
所以今天我们来学习动态规划的思路
首先献上代码
#include
int main()
{
int a[100];
int n, Max = 0, max = 0;//分别定义两和
int c1 = 0, c2 = 0;
int cc1 = 0, cc2 = 0;//记录两组和的起末位置
scanf("%d", &n);//输入数组长度
int i;
for (i = 0; i < n; i++)//循环输入数组并进行判断
{
scanf("%d", &a[i]);
if (i == 0)//初始化两组最大和
{
Max = max = a[i];
continue;
}
if (max > 0)
{
max = max + a[i];
cc2 = i;
}
else if (max <= 0)
{
max = a[i];
cc1 = cc2 = i;
}
if (max >= Max)//判断是否取代
{
Max = max;
c1 = cc1, c2 = cc2;
}
}
printf("%d %d\nMax=%d\n", c1, c2, Max);//输出位置及和
return 0;
}
请首先看代码
下面 我们来分析思路
主要会用到类似数学中数学归纳法的想法
1：我们的两个max分别存储已知的前n个数的和最大子列（后面称为M）
和以第n个数为结尾的和最大子列（后面称为m）
当然M肯定是大于等于m的
2：那么我们来看数组由n边为n+1后
m肯定会变化，我们就根据m的变化，判断是否m>M
大于则取代
那么直到数组全部输入完成
我们就会得到和最大子列
需要注意的是要对m和M初始化的问题
以及能否相同当m<0是
第n+1个数即为新的m
当然还有很多要注意的地方
我简要的先说这些
如果还有什么问题的话评论区留言，我在持续改进。