线性动态规划-最大子序和

一个整数数组，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回最大子序列的和。
例如：
序列：4, -3, 18, -4, 5, -5, -2, -1，则最大子序列和为20。子序列为： 4, -3, 18, -4, 5

解法一：穷举法1

通过三个for循环直接给出所有可能出现的子序列，从中选出一个最大值即可。
但是该方法时间复杂度真的是太大了，达到了O(n³)，有很多操作完成是重复性的操作。

#include <iostream>
using namespace std;

int a[1000];
int maxsequence(int len){
  int maxsum = 0;
  for(int i = 0;i < len;i++){
    for(int j = i;j<len;j++){
      int newsum = 0;
      for(int k = i;k <=j;k++){
        newsum+=a[k];
      }
      if(newsum > maxsum)
        maxsum = newsum;
    }
  }
  return maxsum;
}

int main(){
    int n;
    cin>>n;
    for (int i = 0; i <n; i++)cin>>a[i];
    cout<<maxsequence(n);
}

解法二：穷举法2

它是第一种解法的改进，当我们计算i..j的值时候，i……j-1已经被计算过了，可以直接利用，不用重新计算一次i……j-1。其时间复杂度为O(n²),

#include <iostream>
using namespace std;

int a[1000];
int maxsequence(int len){
  int maxsum = 0;
  for(int i = 0;i < len;i++){
    int newsum = 0;
    for(int j = i;j<len;j++){
      newsum+=a[j];
      if(newsum > maxsum)
        maxsum = newsum;
    }
  }
  return maxsum;
}

int main(){
    int n;
    cin>>n;
    for (int i = 0; i <n; i++)cin>>a[i];
    cout<<maxsequence(n);
  }

解法三：分治法

这个算法的核心就是分治思想。我们假设将我的已经知道的序列分成左右两部分，那么最大子序列存在的位置显然有三种可能：
(1) 左序列
(2) 右序列
(3) 左序列的右部分加上右序列的左部分

显然如果是情况（3），是比较容易算出来的。如果是情况（1）和（2）的话，我们可以将左部和右部当中一个重新的序列计算，那么新的序列又可以分成左右部分，重复以上即可。该算法的时间复杂度了O(n * lg(n))。

#include <iostream>
using namespace std;

int a[1000];
int maxSubarray(int h, int m)
{
    if (h > m)
        return -1;
    if (h == m)
        return max(a[h], 0);
    int j = (h + m) >> 1;
    int wh = 0, wm = 0;
    int wht = 0, wmt = 0;
    for (int i = j; i >= h; i--) {
        wht += a[i];
        wh = max(wh, wht);
    }
    for (int i = j + 1; i <= m; i++) {
        wmt += a[i];
        wm = max(wm, wmt);
    }
    return max(max(maxSubarray(h, j), maxSubarray(j + 1, m)), wh + wm);
}

int main(){
    int n;
    cin>>n;
    for (int i = 0; i <n; i++)cin>>a[i];
    cout<<maxSubarray(0,n-1);
}

解法四：贪心算法

因为当前几项序列的和为负数的话，它一定不能被包括在最大序列中，例如，当首项为-3时，最大连续子序列肯定不会包含它，所以从第二个是开始继续判断，若首项为正数5，第二项为-2的话，由于前两项的加和为正数，所以对序列的增益有效，所以继续向下判断前三项之和，以此类推。该算法的时间复杂度显然就是O(n)。

#include <iostream>
using namespace std;

int a[1000];
int maxsequence(int len){

  int maxsum = a[0];
  int maxnew = a[0];
  for(int i = 1;i < len;i++){
    if(maxnew <= 0)
      maxnew = a[i];
    else
      maxnew += a[i];

    if(maxnew > maxsum)
      maxsum = maxnew;
  }
  return maxsum;
}

int main(){
    int n;
    cin>>n;
    for (int i = 0; i <n; i++)cin>>a[i];
    cout<<maxsequence(n);
    

}

解法五：动态规划

动态规划的思路：

状态表示：
- 令 dp[i] 表示以第 i 个元素结尾的最大子数组的和。
状态转移方程：
- dp[i] = max(nums[i], dp[i-1] + nums[i])
- 解释：对于每个元素 nums[i]，你有两个选择：要么将它加入之前的子数组（即 dp[i-1]）中，要么从当前元素重新开始一个新的子数组。你选择这两者中的较大值作为 dp[i]。
初始条件：
- dp[0] = nums[0]，即第一个元素本身就是最大子数组的和。
最终结果：
- 最大子数组的和为 dp[i] 中的最大值。

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxSubArray(const vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];
    int global_max = dp[0];
    
    for (int i = 1; i < n; i++) {
        dp[i] = max(nums[i], dp[i-1] + nums[i]);
        global_max = max(global_max, dp[i]);
    }
    
    return global_max;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "Maximum Subarray Sum is " << maxSubArray(nums) << endl;
    return 0;
}

代码解析：

在这个实现中，dp[i] 表示以第 i 个元素结尾的最大子数组的和。
状态转移方程仍然是 dp[i] = max(nums[i], dp[i-1] + nums[i])。
最终通过遍历 dp 数组，找到其中的最大值，即为最大子数组的和。
空间优化，通过 current_max 和 global_max 两个变量，我们仅保留了前一个状态的值（即 dp[i-1]），从而节省了存储 dp 数组的空间。

P1115

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

线性动态规划-最大子序和

动态规划的思路：

代码解析：