您现在的位置是:首页 >学无止境 >求最大字段和(穷举法、动态规划、分治法)网站首页学无止境

求最大字段和(穷举法、动态规划、分治法)

官乐 2024-06-17 11:19:25
简介求最大字段和(穷举法、动态规划、分治法)


1、案例要求

给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列形如:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QAbrqvEv-1684376003140)(file:///C:UsersljpAppDataLocalTempksohtml4224wps1.png)]
的子段和的最大值。当所有整数均为负数时定义其最大子段和为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]中元素含义、找出数组元素之间的关系式、找出初始值较为关键,需充分理解题意再开始进行代码实现!

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。