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

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

解法一:穷举法1

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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(n2),

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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))。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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);
    

}

解法五:动态规划

动态规划的思路:

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

代码实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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_maxglobal_max 两个变量,我们仅保留了前一个状态的值(即 dp[i-1]),从而节省了存储 dp 数组的空间。

P1115

Scroll to Top