CSGNAK的博客

【数据结构】最大子序列求和

数据结构
Word count: 223Reading time: 1 min
2021/09/13 Share

2021年数据结构Week1.2作业。

还没有写完。

给定整数序列 a1,a2,…,an，求 j > k 时，$\sum_{i=k}^{j}$ai的最大值

给出算法及其时间复杂度分析，并尝试设计时间复杂度更优的算法

如果要求给出 k, j 的值，如何改进算法?

参考链接：[1].力扣；[2].博客-始终

[解法一]枚举法

思路

从a[0]开始，枚举所有的子序列。计算所有子序列的和，然后取出最大值。

时间复杂度 O(n^2); 空间复杂度 O(1);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int MaxSubarraySum(list){
  len = sizeof(list);
  max = -max(list);
    sum = 0;
    for(i=0;i<len;i++){
      sum = 0;
      for(j=i;j<len;j++){
        sum += list[j];
        if(sum > max){
          max = sum;
        }
      }
    }
  return max;
}

然后就超时了（逃。

[解法二]分治法

思路

最大子序列只会出现在三个位置。

CATALOG
  1. 1. [解法一]枚举法
    1. 1.1. 思路
    2. 1.2. 代码
  2. 2. [解法二]分治法
    1. 2.1. 思路
Total : 9
2021
数据结构 心得 计算系统概论 大二上
数据结构