算法设计与分析 动态规划 实验报告
武 夷 学 院
实验报告
数学与计算机系
实验四 动态规划算法（2学时）
一、实验目的与要求
1、熟悉最长最大字段和问题的算法；
2、进一步掌握动态规划算法；
二、实验题
若给定n个整数组成的序列a1，a2，a3，……an，求该序列形如ai＋ai＋1＋……＋an的最大值。
三、实验步骤
1. 打开netbeans输入程序代码：
package dp;
public class DP {
public static int MaxSum(int n,int[] a,int besti,int bestj){ int sum=0;
for(int i=1;i
for(int j=i;j
{
int thissum=0;
for(int k=i; k
if(thissum>sum)
{
sum=thissum;
besti=i;
bestj=j;
}
}
return sum;
}
public static int maxSubLen(int *a,int aSize,int m,int k) {
int countMax=0;
int subLeft=0;
int countTemp=1;
mNode aMax={a[0],0};
mNode aMin={a[0],0};
int leftBound=0;
for (int i=1;i
{
{
aMin.value=a[i];
aMin.position=i;
if
(m
{
countTemp++;
}
else
{
if (countMax
{
countMax=countTemp;
subLeft=leftBound;
}
aMax.value=a[i];
aMax.position=i;
for(int j=i-1;j>=leftBound;j--)
{
if (a[j]-aMin.valueleftBound=j+1;
countTemp=i-j;
break;
}
else
{
if (aMax.value
{
aMax.value=a[j];
aMax.position=j;
}
}
}
if (aSize-leftBound
{
break;
}
}
}
else if (aMax.value
{
aMax.position=i;
if
(m
{
countTemp++;
}
else
{
if (countMax
{
countMax=countTemp;
subLeft=leftBound;
}
aMin.value=a[i];
aMin.position=i;
for(int j=i-1;j>=leftBound;j--)
{
if (aMax.value-a[j]leftBound=j+1;
countTemp=i-j;
break;
}
else
{
if (a[j]
{
aMin.value=a[j];
aMin.position=j;
}
}
}
if (aSize-leftBound
{
break;
}
}
}
else
{
countTemp++;
}
}
if (countMax
{
countMax=countTemp;
subLeft=leftBound;
}
for (int i=subLeft;i
System.out.print a[i];
}
return countMax;
}
}运行
四、实验结果
按F6,输入数据，回车
五、实验结论
通过本次试验我熟悉深刻的掌握了动态规划算法。