OJ P1268 连续子段的最大和
目录
方法一：暴力枚举
方法二：动态规划（dynamic programming）
题目描述
从一组数据（长度为 n，其中 n <= 10000，数据的值都大于 -60000）中找出连续的一段数，使得这段数的和最大。
输入描述
第一行是一个正整数 n，表示数据的个数，从第二行开始是 n 个数据。
输出描述
一行，子段的最大和。
样例输入
5
1 -3 4 1 -9
样例输出
5
方法一：暴力枚举
因为需要遍历所有的情况，优先想到暴力枚举 ，实现很简单
完整AC代码如下
#include
using namespace std;
//连续子段的最大和，需要遍历，优先想到暴力枚举
int main()
{int n;cin>>n;int a[n];for(int i=0;i>a[i];int sum=0;int max=a[0]; //max存放连续子段和的最大值 for(int i=0;i max的值不能设置为0，因为可能所有的值都是负数
此方法时间复杂度为O(n²）
方法二：动态规划（dynamic programming）
因为遍历需要很大的时间复杂度，当数据量较大时会超时，因此可以采用dp来优化！
首先需要了解什么是动态规划？
动态规划原理：
动态规划是一种解决多阶段决策问题的优化方法，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。
动态规划求解的问题的一般要具有3个性质：
最优性原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优性原理。
无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）。
实际应用中简化的步骤：
- 分析最优解的性质，并刻画其结构特征。
- 递归的定义最优解。
- 以自底向上或自顶向下的记忆化方式计算出最优值。
- 根据计算最优值时得到的信息，构造问题的最优解。
针对这题，对于含有n个元素的数组a，构造同样含有n个元素的数组dp，其中dp[i]表示前i个元素中最大连续子段的和，则dp[i-1]表示前（i-1）个元素中最大连续子段的和。
要求连续子段的最大值，对于每一个元素a[i]，要么加，要么不加，不加a[i]存储在dp[i-1]中，加a[i]或者直接选择a[i]的值更大时，将值存储在dp[i]中
由此可得递归方程：
当i=0时，dp[0] = 0；
当i>0时，dp[i] = MAX { dp[i-1] + a[i] , a[i] };
最后只需找到dp数组中的最大值即可（可采用简单的for循环，也可采用STL中的sort排序）
完整AC代码如下：
#include
#include
using namespace std;int MAX(int a,int b){return a>b?a:b;
} int a[10005];
int dp[10005]; //dp[i]表示前i个元素中最大连续子段的和
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];dp[0]=0;for(int i=1;i<=n;i++)dp[i]=MAX(dp[i-1]+a[i],a[i]);sort(dp+1,dp+1+n); //也可采用简单的for循环，找出dp数组中的最大值 cout< 不难发现此方法的时间复杂度为O(n)
有关sort排序的用法会陆续更新，总之STL尊滴很好用！
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！