锐客网

  1. 首页 > it技术 > >

动态规划---例题3.最大子段和问题

本题与力扣主站53题 --- 最大子序和相同.
一.问题描述 给定n个整数（可能有负数）组成的序列a1,a2,…an, 求子段和ai+ai+1+…+aj的最大值。
当所有整数均小于零时，定义其子段和为0。
最大值为max{0, maxΣak}
例：(-2, 11, -4, 13, -5, -2)的最大子段和为20
二.解题思路 1.朴素暴力
我们使用数组a存放n个整数，sum、besti、bestj分别存放最大子段和及其始末下标。
时间复杂度: T(n) = O(n^3)

int MaxSum(int n, int *a, int &besti, int &bestj) { int sum = 0; for(int i=1; i<=n; i++) for(int j=i; j<=n; j++)//i,j边界确定下来 { int thissum = 0; for(int k=i; k<=j; k++) thissum += a[k]; //(用k来遍历a[i,j]求和)每次k只是加一,所以重复计算了a[i]~a[j]的和 if(thissum > sum) { sum = thissum; besti = i; bestj = j; } } return sum; }

对上述方法的改进:
我们用k来遍历a[i...j]求和,每次k只是加一,所以重复计算了a[i]~a[j]的和.故我们可以省略一个循环,每次j++后,只要把最后一个a[k] (此时k=j)加上就好.
时间复杂度: T(n) = O(n^2)
int MaxSum2(int n, int *a, int &besti, int &bestj) { int sum = 0; for(int i=1; i<=n; i++) { int thissum = 0; for(int j=i; j<=n; j++) { thissum += a[j]; if(thissum > sum) { sum = thissum; besti = i; bestj = j; } } } return sum; }

2.分治算法
将a[1:n]分为a[1:n/2]和a[n/2+1:n]两部分,一共分三种情形：
动态规划---例题3.最大子段和问题
文章图片

  • 最大子段和在左半部分，比如LS
  • 最大子段和在右半部分，比如RS
  • 最大子段和跨越两部分，为S1+S2，并且左半部分的最右端元素一定在S1中，右半部分的最左端元素一定在S2中。
最大子段和等于: Max(LS, RS, S1+S2)
时间复杂度:T(n) = O(n log n)
int MaxSubSum13(int *a, int left, int right) { int sum = 0; if(left == right) sum = a[left]>0 ? a[left]:0; else { int center = (left+right)/2; int leftsum = MaxSubSum13(a, left, center); int rightsum = MaxSubSum13(a, center+1, right); int s1 = 0; int lefts = 0; for(int i=center; i>=left; i--)//从center位置往左和往右分别找到最大值 { left += a[i]; if(lefts > s1) s1 = lefts; } int s2 = 0; int rights = 0; for(int i=center+1; i<=right; i++) { right += a[i]; if(rights > s2) s2 = rights; } sum = s1+s2; if(sum

计算时间：递归方程
  • T(n)=O(1) n<=C
  • T(n)=2T(n/2)+O(n) n > C
    故T(n)=O(n logn)
3.动态规划(重点)
假设nums数组长度为n, 我们用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」，
那么很显然我们要求的答案就是：max(0 因此我们只需要求出每个位置的 f(i)，然后返回 f 数组中的最大值即可。那么我们如何求 f(i) 呢？
我们可以考虑 nums[i], 单独成为一段还是加入f(i-1) 对应的那一段.这取决于 nums[i] 和 f(i-1) + nums[i] 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程:
  • f(i) = max(nums[i], f(i-1) + nums[i]) 1<=i<=n
时间复杂度: T(n) = 0(n)
int maxSubArray3(vector& nums) { if(nums.size()==0) return {}; int n = nums.size(); int pre = 0; int maxSum = nums[0]; for(int i=0; i

本篇文章参考我的老师毕方明《算法设计与分析》课件. 【动态规划---例题3.最大子段和问题】欢迎大家访问我的个人博客 --- 乔治的编程小屋,和我一起为大厂offer 努力吧!

    推荐阅读


    上一篇：Android HAL 开发 (2)

    下一篇：Linux——基础命令用法（上）