动态规划1：最大子段和问题到最大子矩阵问题（一）：最大子段和问题详谈

本文主要是介绍动态规划1：最大子段和问题到最大子矩阵问题（一）：最大子段和问题详谈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。

例如：

对于6 -1 5 4 -7，最长子段和为14，是6+（-1）+5+4

最直接的方法：穷举法：对数组的每一个i到j和都求出来，求出最大值，算法很好想

int result=0;
for(int i=0;i<n;i++){for(int j=i;j<n;j++){int sum=0;for(int k=i;k<=j;k++)sum+=a[k];result=max(result,sum);}
}
return result;

可以看出，此方法时间复杂度为O(n^3)

然后我们试着对其进行优化，发现，代码中每次都对i到j进行求和，我们可以先将结果保存起来，当然可以这么定义，定义一二维数组sum[i][j]，表示i到j的和，但是i到j的和其实也就是0到j的和再减去0到i的和，只要用一个一维数组sum[i]表示0到i的和，然后用sum[j]-sum[i-1]（因为还要包括i，所以要i-1）就是i到j的和了，所以经过改进的算法如下：

int result=0;
int sum[n];
sum[0]=a[0];
for(int i=1;i<n;i++)sum[i]=sum[i-1]+a[i];
for(int i=0;i<n;i++){for(int j=i;j<n;j++){result=max(result,sum[j]-sum[i-1]);}
}
return result;

在这里注意处理好0位置就好了，时间复杂度为O(n^2)

接着，我们想想用分治的思想来解决此题：

我们不妨从小规模数据分析，当序列只有一个元素的时候，最大的和只有一个个可能，就是选取本身；

当序列有两个元素的时候，只有三种可能，选取左边元素、选取右边元素、两个都选，这三个可能中选取一个最大的就是当前情况的最优解；

对于多个元素的时候，最大的和也有三个情况，从左区间中产生、从右区间产生、左右区间各选取一段。因此不难看出，这个算法是基于分治思想的，每次二分序列，直到序列只有一个元素或者两个元素。当只有一个元素的时候就返回自身的值，有两个的时候返回3个中最大的，有多个元素的时候返回左、右、中间的最大值。因为是基于二分的思想，所以时间效率能达到O(nlgn)。

int divide(int a[],int left,int right)
{if(left==right)return v[left];int mid=(left+right)/2;int lsum=divide(a,left,mid);int rsum=divide(a,mid+1,right);int lmax=INT_MIN;int sum=0;for (int k=mid;k>=left;k--){//从mid向前找一个最大的连续子段sum+=a[k];lmax=max(lmax,sum);}sum=0;int rmax=INT_MIN;for (int k=mid+1;k<=right;k++){//从mid向后找一个最大的连续子段sum+=a[k];rmax=max(rmax,sum);}sum=s1+s2;return max(sum,max(lsum,rsum));//返回三个中的最大值
}

最后我们采取动态规划的方法来解决此题，

动态规划有两种思路：

1、dp[i]表示0~i（包括i）的最长子序列和，有

dp[i]=max(A[i],dp[i-1]+A[i])，则result=max{dp[t]}

因为dp[i]与dp[i-1]的关系，可以直接使用一个变量代替数组，然后从dp[0]到dp[n]选出最大的那个就是答案了，时间复杂度降为了O(n)。

int DP(int a[],int n){int dp=0,maxSum=INT_MIN;for(int i=0;i<n;i++){dp=dp>0?dp+a[i]:a[i];maxSum=max(maxSum,dp); } return maxSum; 
}

当然，从后向前也一样

int DP(int A[], int n) {int dp=0,maxSum=INT_MIN;  for(int i=n-1;i>=0;i--)  {  dp=dp>0?dp+A[i]:A[i];  maxSum=max(maxSum,dp);   }   return maxSum; }

2、dp[i]表示0~i（不一定包括i）的最长子序列和，有

设sum[i]表示A0~Ai的和

dp[i]=max{dp[i-1],sum[i]-min{sum[t]}}  0<=t<i

class Solution {  
public:  int maxSubArray(int A[], int n) {  int dp=INT_MIN;  int minV=INT_MAX;  int sum=0;  for(int i=0;i<n;i++){  minV=min(minV,sum);  sum+=A[i];  dp=max(dp,sum-minV);  }  return dp;  }  
};  

2（续）dp[i]表示i到n（不一定包括i）的最长子序列和，有

设sum[i]表示A0~Ai的和

dp[i]=max{dp[i+1],max{sum[t]}-sum[i-1]}    i<=t<=n

因为从后向前遍历，所以sum数组必须事先生成

class Solution {
public:int maxSubArray(int A[], int n) {int sum[n];for(int i=0;i<n;i++)sum[i]=i==0?A[i]:sum[i-1]+A[i];int dp=INT_MIN;int maxV=INT_MIN;for(int i=n-1;i>=0;i--){maxV=max(maxV,sum[i]);dp=max(dp,maxV-(i==0?0:sum[i-1]));}return dp;}
};

拓展问题：

1、最长2子段和问题，从序列中找到两组子序列，使得和最大

思路：

先找到0到i的最长子序列和dp1[i]，再找到i到n的最长子序列和dp2[i]，

则max=max{max,dp1[i]+dp2[i]}

参见：LeetCode OJ:Best Time to Buy and Sell Stock III

注：注意i是否可以重复，即序列1的最后位置和序列2的首位置是否可以重复，此LeetCode题中是可以重复的

2、最大连续乘积子串

参见：第二十八章：最大连续乘积子串

这篇关于动态规划1：最大子段和问题到最大子矩阵问题（一）：最大子段和问题详谈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---