动态规划法:
其与分治法类似,基本思想也是将待求解的问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是独立的。
我们用一个表来记录所有已经解决的自问题的答案。动态规划法通常用于求解具有某种最优性质的问题。在这类问题中,每个解都对应一个值,我们希望找到具有最优值的那个解。
问题:
由给定的n个整数(可能为负整数)组成的序列a1,a2,...,an,求该序列的子段和最大值。当所有整数均为负数时定义其最大子段和为0。例如:(-2,11,-4,13,-5,-2)时,最大字段和为11 + -4 + 13 = 20
代码:
#include <stdio.h>
// 定义b[j]为a[i]...a[j]的最大子段和。则当b[j-1] > 0时,b[j] = b[j-1] + a[j],否则b[j] = a[j]
int maxSum(int *v, int n) {
int sum = 0, b = 0;
int i;
for(i = 1; i <= n; i++) {
if(b > 0) b += v[i];
else b = v[i];
if(b > sum) sum = b;
}
return sum;
}
void main() {
int a[] = { 0, -2, 11, -4, 13, -5, -2 };
printf("%d\n", maxSum(a, 6));
}
分享到:
相关推荐
用动态规划法求解最大子段和问题 C语言实现
蛮力法、分治法和动态规划法设计最大子段和问题的算法,一、试分别利用蛮力法、分治法和动态规划法求解最大子段和问题,要求写出C/C++程序实现和算法的效率分析。程序运行结果要同时给出最大子段和的值以及由哪个子段...
算法设计与分析中最大子段和问题的蛮力法、分治法和动态规划法
蛮力法分治法动态规划法求最大子段和,已测试通过
最近对问题 最大子段和(分治法) 最长公共子序列问题 最大子段和(动态规划)
蛮力法、分治法和动态规划法设计最大子段和问题的算法.doc
动态规划实例编程,求最大子段和 问题描述:若给定n个整数组成的序列a1,a2,a3,……an,求该序列形如ai+ai+1+……+an的最大值。
求最大子段和
【问题描述】使用分治递归算法解最大子段和问题,具体来说就是,将序列分为长度相等的左右两段,分别求出这两段的最大子段和,包含左右部分子段的最大子段和,求这三种情况得到的最大子段和的最大值。 【输入形式】...
用蛮力法,分治法,动态规划法求最大子段和问题
用动态规划法和分治法 自己写的 可以运行
算法设计与分析--求最大子段和问题(蛮力法、分治法、动态规划法) C++实现.rar
分别用三重循环,分治法和动态规划算法来解决最大子段和问题,并比较三个算法效率的差异。内含c++源代码和实验报告说明
利用动态规划法求一个数组最大的子段和,并输出该最大字段(JAVA实现)
用动态规划法,C语言编写的解决最大字段和的问题
算法最大子段和问题,蛮力法,分治法,动态规划法
分别用蛮力法、分治法、动态规划法设计的最大子段和问题的算法。用VC++ 6.0运行。
配套王红梅的《算法设计与分析》中 第六章的实验项目 最大字段和问题,暂时只写出蛮力法。分治法 和动态规划法还将继续研究。逐渐上传~
编程实现最大子段和问题的求解(分别采用分治法和动态规划法求解) 编程实现最长公共子序列(LCS)问题的求解 设计算法求解数字三角形问题,并编程实现。(P90算法实现题3-7)