题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。

解法

1. 暴力法

思路：枚举所有可能的子序列的和。通过三重循环每次求出一个数组下标范围为[index1, index2]的子序列的和，每次求出和后进行判断，更新最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
  public int FindGreatestSumOfSubArray(int[] array) {
    if (array == null) return 0;
    // 初始化最大值
    int max = array[0];
    int sum;
    // 遍历区间下界索引
    for (int index1 = 0; index1 < array.length; index1++) {
      // 遍历区间上界索引
      for (int index2 = index1; index2 < array.length; index2++) {
        sum = 0;
        // 计算区间[index1, index2]的和
        for (int i = index1; i <= index2; i++) {
          sum += array[i];
        }
        // 更新最大值
        if (max < sum) {
          max = sum;
        }
      } 
    }
    return max;
  }
}

时间复杂度为$O(n^3)$，空间复杂度为$O(1)$

2. 优化暴力法

思路：去掉第三层循环，在第二层遍历区间上界的时候就进行累加判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
  public int FindGreatestSumOfSubArray(int[] array) {
    if (array == null) return 0;
    // 初始化最大值
    int max = array[0];
    int sum;
    // 遍历区间下界索引
    for (int index1 = 0; index1 < array.length; index1++) {
      // 遍历区间上界索引
      sum = 0;
      for (int index2 = index1; index2 < array.length; index2++) {
        sum += array[index2];
        if (max < sum) {
          max = sum;
        }
      } 
    }
    return max;
  }
}

时间复杂度为$O(n^2)$，空间复杂度为$O(1)$

3. 动态规划

重头戏来了👊，这道题是动态规划的经典题型。那么，什么是动态规划呢？

按照定义，动态规划（Dynamic Programming）是把一堆大问题拆成一堆小问题（最优解肯定是由最优的子解转移而来的思想），而且这些小问题会被重复调用。

动态规划一般分为四个过程：

  • 划分状态：即划分子问题
  • 状态确定：告诉计算机理解子问题
  • 状态转移：父问题如何由子问题推导出来
  • 确定边界：确定初始状态是什么？最小的子问题是什么？最终状态又是什么？

在这个问题中

  • 划分状态：我们可以将问题——求大小为n的数组的最大连续子序列和划分成求解大小为n-1, n-2, …, i的最大连续子序列和。
  • 状态确定：建立dp集合，dp[i]表示前i个数的最大连续子序列和。
  • 状态转移：dp[i-1]是前i-1个数的最大连续子序列和，如果它是正数，那么正数加任意一个数一定比本身大；如果是负数，说明将第i个数反而减小了，所以直接取自身。
    $dp[i] = max(array[i], array[i] + dp[i - 1])$
  • 确定边界：大小为1的数组的最大连续子序列和就是元素本身😀。最终的最大连续子序列和就是这里面的最大值（可以使用max变量直接更新。）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

public class Solution {
  public int FindGreatestSumOfSubArray(int[] array) {
    if (array == null) return 0;
    // 状态确定
    List<Integer> dp = new ArrayList<>();
    // 确定边界
    dp.add(array[0]);
    int max = array[0];
    // 状态转移
    for (int i = 1; i < array.length; i++) {
      if (dp.get(i - 1) < 0) {
        dp.add(array[i]);
      } else {
        dp.add(array[i] + dp.get(i - 1));
      }
      if (max < dp.get[i]) {
        max = dp.get[i];
      }
    }
    return max;
  }
}

时间复杂度为$O(n)$，空间复杂度为$O(n)$

4. 优化动态规划

我们能够发现，上面的dp空间在计算时实际只用到了dp[i-1]的值，所以没必要建立一个集合，使用一个变量就好啦🤪

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
  public int FindGreatestSumOfSubArray(int[] array) {
    if (array == null) return 0;
    // 记录i-1个元素的连续子序列和
    int curSum = array[0];
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
      if (curSum < 0) {
        curSum = array[i];
      } else {
        curSum += array[i];
      }
      if (max < curSum) {
        max = curSum;
      }
    }
    return max;
  }
}

时间复杂度为$O(n)$，空间复杂度为$O(1)$

参考