 | 一、问题描述
输入一个整形数组，数组里可以有正数或负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。
第一次遇到这道题是参加x迅的笔试。题目中给出了两种解法，让填空。
二、简单解
拿到这道题，如果不考虑性能和复杂度，最简单的方法就是穷举。穷举出所有的子数组，并求出他们的和，返回最大值。不过，复杂度为O(n3)，不符合题目的要求（复杂度On）
[cpp] view plaincopyprint?
int max_sum(int *arr, int len){
int max, sum;
for(int i = 0; i < len; i++) {
for(int j = i; j < len; j++) {
sum = 0;
for(int k = i; k <= j; k++) {
sum = sum + arr[k];
if(sum > max) {
max = sum;
}
}
}
}
if(max == 0) {
return max(arr, len);
}
return max;
}
int max_sum(int *arr, int len){
int max, sum;
for(int i = 0; i < len; i++) {
for(int j = i; j < len; j++) {
sum = 0;
for(int k = i; k <= j; k++) {
sum = sum + arr[k];
if(sum > max) {
max = sum;
}
}
}
}
if(max == 0) {
return max(arr, len);
}
return max;
}
三、复杂度为N2的解
观察上面的代码，我们使用了3个for循环。其中最内侧的for循环主要是控制每个字序列的长度，由于我们在计算的过程中，已经保存了当前最大字序列和，字序列的长度N对我们来说意义不大，因此完全可以撤消最内侧的循环。只按每个字序列起始位置来计算最大和。这样得到一个复杂度为N2的解。
[cpp] view plaincopyprint?
int max_sum2(int *arr, int len){
int sum, max = 0;
for(int i = 0; i < len; i++) {
sum = 0;
for(int j = i; j < len; j++) {
sum = sum + arr[j];
if(max < sum) {
max = sum;
}
}
}
if(max == 0) {
return max(arr, len);
}
return max;
}
int max_sum2(int *arr, int len){
int sum, max = 0;
for(int i = 0; i < len; i++) {
sum = 0;
for(int j = i; j < len; j++) {
sum = sum + arr[j];
if(max < sum) {
max = sum;
}
}
}
if(max == 0) {
return max(arr, len);
}
return max;
}
四、更低复杂度的探索
至此，我们已经得到一个复杂度为N2的解法。那么有没有更低复杂度的算法呢？在N2的算法中，我们遍历了从0到len-1开始的字序列，求出每种情况下得到的最大字序列和。那么我们有没有可能去掉这个循环呢？考虑使用动态规划的思想，记max_sum为从0到i的子序列的最大和，那么可以得到递推式：
[cpp] view plaincopyprint?
if max_sum > 0
then
if arr[i+1] > 0
then max_sum[i+1] = max_sum + arr[i+1];
else
max_sum[i+1] = max(0, arr[i+1])
if max_sum > 0
then
if arr[i+1] > 0
then max_sum[i+1] = max_sum + arr[i+1];
else
max_sum[i+1] = max(0, arr[i+1])
利用这种思路得到一个线性时间的解答：
[cpp] view plaincopyprint?
int max_sum3(int *arr, int len) {
int sum, max;
max = sum = 0;
for(int i = 0; i < len; i++) {
sum += arr;
if(sum < 0) {
sum = 0;
}
if(sum > max){
max = sum;
}
}
if(max == 0) {
return max(arr, len);
}
return max;
}
int max_sum3(int *arr, int len) {
int sum, max;
max = sum = 0;
for(int i = 0; i < len; i++) {
sum += arr;
if(sum < 0) {
sum = 0;
}
if(sum > max){
max = sum;
}
}
if(max == 0) {
return max(arr, len);
}
return max;
}
至此，我们得到一个时间复杂度On，空间复杂度O1的解。
| |
