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

一个整数数组,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回最大子序列的和。
例如:
序列: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);
    

}
Scroll to Top