您现在的位置是:首页 >学无止境 >求最大字段和(穷举法、动态规划、分治法)网站首页学无止境
求最大字段和(穷举法、动态规划、分治法)
简介求最大字段和(穷举法、动态规划、分治法)
目录
1、案例要求
给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列形如:
的子段和的最大值。当所有整数均为负数时定义其最大子段和为0。
分别采用穷举法、分治法、动态规划法完成。
2、算法设计与实现
2.1 穷举法
2.1.1 算法设计思路
通过定义遍历子段起始位置与子段和长度将所有情况计算一遍,从而得到最大子段和;
2.1.2 代码实现
时间复杂度:O(n2)
public static int qiuju(int[] nums){
int len=nums.length;
if(len==1) return nums[0];
int res=nums[0];
//起始位置
for(int i=0;i<len;i++){
//子段和长度
int max=0;
for(int j=1;j<=len-i;j++){
max+=nums[i+j-1];
res=Math.max(res,max);
}
}
return res;
}
2.2 动态规划
2.2.1 算法设计思路
将问题转移为求以各数组元素结尾的子段最大和,对每个序列元素求结尾最大子段和时,通过比较前一个元素结尾最大子段和是否为负数,是则重新开始,否则拼接到上一个连续子段,最后比较所有的结尾最大子段和得到最大子段和。
2.2.2 实现代码
时间复杂度:O(n)
public static int dynamicProgram(int[] nums){
int len=nums.length;
if(len==1) return nums[0];
//状态转移数组,以nums[i]结尾的连续子数组的最大和
int[] dp=new int[len];
dp[0]=nums[0];
for(int i=1;i<len;i++){
if(dp[i-1]<0){
//前一个数组元素结尾的最大和为负,重新开始
dp[i]=nums[i];
}else{
//拼接到上一个连续子数组
dp[i]=dp[i-1]+nums[i];
}
}
int res=nums[0];
//遍历dp数组,找到最大和所在结尾nums元素,
// 并返回最大和
for(int num:dp){
res=Math.max(res,num);
}
return res;
}
2.3 分治法
2.3.1 算法实现思路
将序列分为三部分进行求解,分别是[left,mid]、[mid,mid+1]、[mid+1,right],分别对三部分求最大子段和,最后比较三部分得到最大子段和。
2.3.2 代码实现
时间复杂度:O(nlog2n)
public static int fenzhi(int[] nums,int left,int right){
//分到中间位置重合,结束递归
if(left==right){
return nums[left];
}
//确定中间位置
int mid=left+(right-left)/2;
//返回三种情况的最大值
return Max3(fenzhi(nums,left,mid),
fenzhi_mid(nums,left,mid,right),
fenzhi(nums,mid+1,right));
}
public static int fenzhi_mid(int[] nums,int left,int mid,int right){
int sum=0;
//确定左边最大和
int left_sum=Integer.MIN_VALUE;
//从中间往左遍历,不能从左开始
for(int i=mid;i>=left;i--){
sum+=nums[i];
left_sum=Math.max(sum,left_sum);
}
sum=0;
//确定右边最大和
int right_sum=Integer.MIN_VALUE;
for(int i=mid+1;i<=right;i++){
sum+=nums[i];
right_sum=Math.max(right_sum,sum);
}
//返回左右之和
return left_sum+right_sum;
}
public static int Max3(int n1,int n2,int n3){
//返回三数之和最大值
return Math.max(n1,Math.max(n2,n3));
}
3、总结
动态规划的算法思路与代码实现较难,其适用于解最优化问题,其求解三大步骤:定义数组dp[i]中元素含义、找出数组元素之间的关系式、找出初始值较为关键,需充分理解题意再开始进行代码实现!
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。