最大连续子数组

问题描述

给定一个包含正数和负数的数组，找出这个数组中一个连续的子数组，使得这个子数组之和最大

这个问题看起来很普通但是很有意思，我想到了2种解法，但是第三种解法非常精妙，以下将分别介绍这三种算法

暴力破解

思路很简单，给子数组定义一个起点一个终点，在原数组中移动子数组的这2个端点，计算子数组之和，然后找出最大值

代码如下：

lss1.rs

use std::isize::MIN as MIN_VALUE;
use std::cmp::max;

pub fn max_seq_sum_v1(arr: Vec<isize>) -> isize {
    let l = arr.len();
    let mut best = MIN_VALUE;

    for i in 0..l {
        for j in i..l {
            let mut sum = 0;
            for k in i..j + 1 {
                sum += arr[k];
            }
            best = max(sum, best);
        }
    }
    return best;
}

很显然这个算法很低效，有3重循环，而且有很多重复计算

更优的暴力破解法

在上面的暴力破解算法中，每次移动i, j的时候都要额外定义一个k遍历从而得到i到j的数组之和，这导致很多不必要的重复计算，如i=0, j=2和i=0, j=1时，重复计算了i=0, j=0这部分。优化后的代码如下：

lss2.rs

use std::cmp::max;
use std::isize::MIN as MIN_VALUE;

pub fn max_seq_sum_v2(arr: Vec<isize>) -> isize {
    let l = arr.len();
    let mut best = MIN_VALUE;

    for i in 0..l {
        let mut sum = 0;
        for j in i..l {
            sum += arr[j];
            best = max(sum, best);
        }
    }

    return best;
}

在i和j的循环中，保存上次求和的结果，每次j往后移动一位，利用上次的结果只需要一次计算就能完成，之前在刷欧拉项目第50题-连续素数和的时候用到过这种优化方式，类似求i到j之间和的问题应该都能用这种方法优化

精妙的线性时间算法

这个办法一般人应该很难想到，我个人觉得算法很精妙实现方式也很精妙，代码如下：

lss3.rs

use std::cmp::max;
use std::isize::MIN as MIN_VALUE;

pub fn max_seq_sum_v3(arr: Vec<isize>) -> isize {
    let l = arr.len();
    let mut largest = MIN_VALUE;
    let mut sum = 0;

    for i in 0..l {
        sum = max(arr[i], sum + arr[i]);
        largest = max(largest, sum);
    }
    return largest;
}

只用了一次循环，所以时间复杂度是O(n)，这个算法的意思是，当一个连续子数组结尾在i处的时候，子数组要么是arr[i]，要么是sum+arr[i]，sum可以理解为包含了上一个连续子数组的和，然后不断和已知的最大子数组和比较，等遍历完之后就能知道整体最大子数组和是多少了

虽然这个线性时间算法很优美，但是还是有缺陷的，一次循环没法定位子数组头尾，所以如果要返回对应子数组的头尾就不能做到了，聪明的你觉得是这样吗？