欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

动态规划-最大子段和

程序员文章站 2022-07-12 08:37:56
...

算法思想:动态规划
实际问题:最大子段和
编写语言:Java


前言

最大子段和有多种解法,暴力**法是最简单的,但时间复杂度较高,最少需要 O(n^2),未改进的算法为 O(n^3);而且暴力**这种思路对学习算法是没有帮助的。因此个人并未实现。仅对分治法和动态规划两种思路进行了实现。分治法的解决思路详见分治法-最大子段和,分治法解决最大子段和问题需要的时间复杂度为 O(nlogn),而本篇博文是采用动态规划的思路,动态规划解决最大子段和问题需要的时间复杂度为 O(n)。是最好的一种解决办法。

问题描述

给定n个整数(可能为负数)组成的序列 a[1],a[2],a[3],…,a[n], 求该序列如 a[i]+a[i+1]+…+a[j] 的子段和的最大值。当所给的整数均为负数时定义子段和为0,依此定义,所求的最优值为: Max{0,a[i]+a[i+1]+…+a[j]}, 1<=i<=j<=n 例如,当(a[1],a[2],a[3],a[4],a[5],a[6])=(-2,11,-4,13,-5,-2) 时,最大子段和为20。

递归结构

设 b[j] 存储的是 A[i:j] 的最大字段和,其中 1 <= i <= j,再定义一个 sum 存储最终结果,那么:

  1. 当 b[j - 1] <= 0,b[j] = a[j],即当目前子序列 A[i:j - 1] 的和为负数时,给和不停的赋新值,直到和为正。
  2. 当 b[j - 1] > 0,b[j] = b[j - 1] + a[j],即当目前子序列 A[i:j - 1] 的和为正时,加上子序列中的下一个数,得到一个新的和 b[j]。
  3. 将 b[j] 和 sum 比较,若 b[j] > sum,那么给 sum 赋新值 b[j];若 b[j] < sum,俺么保持 sum 值不变。通过这种方式来保持 sum 为子序列的最大值。

Java代码

public class MaxSubsequenceSum
{
    public static void main(String[] args)
    {
        int[] a = new int[]{-2, 11, -4, 13, -5, -2};
        int result = maxSubSum(a);
        System.out.println("maxSubSum(a) = " + result);
    }
    
    public static int maxSubSum(int[] a)
    {
        int sum = 0, b = 0;
        for(int i = 0; i < a.length; i++)
        {
            if(b > 0)
                b += a[i];
            //当 b <= 0 时,不断赋新值,相当于跳过了负数
            else
                b = a[i];
            if(b > sum)
                sum = b;
        }
        return sum;
    }
}

运行结果

动态规划-最大子段和