Cracking Coding Interview - 16.17 Contiguous Sequence

2019-09-15 2 分钟阅读 ARTS-A

Contiguous Sequence: You are given an array of integers (both positive and negative). Find the contiguous sequence with the largest sum. Return the sum.

EXAMPLE

1
2

Input:  2, -8, 3, -2, 4, -10
Output: 5 (i.e, {3, -2, 4})

Hints: #537, #551, #567, #594, #614

解法1

可以先把数组变成一个累加数列，当前index sum值 = sum(当前元素 + 所有前面元素的)。

1
2

array:    2, -8, 3,  -2,  4, -10
sumarray: 2, -6, -3, -5, -1, -11

然后我们知道array[n~m]元素之和 = sumarray[m] - sumarray[n - 1]，所以在计算区间之和的时候就能够减少很多循环。

如果给定一个index m，那么它能够形成的连续数列可以是：

1
2
3
4
5
6

array[0...m]   -> sumarray[m]
array[1...m]   -> sumarray[m] - sumarray[0]
array[2...m]   -> sumarray[m] - sumarray[1]
...
array[m-1...m] -> sumarray[m] - sumarray[m-2]
array[m...m]   -> sumarray[m] - sumarray[m-1]

那么我们可以从第一个元素开始，计算它所有的连续数列所能组成的和，然后是第二个元素，第三个元素。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int maxContiguous(int[] array) {
  int[] sumarray = array.clone();
  // 构建累加数列
  for (int i = 1; i < sumarray.length; i++) {
    sumarray[i] = sumarray[i] + sumarray[i - 1];
  }
  // 找到最大的连续数列值
  int maxSum = Integer.MIN_VALUE;
  for (int i = 0; i < sumarray.length; i++) {
    for (int j = -1; j < i; j++) {
      int sum = 0;
      if (j == -1) {
        sum = sumarray[i];
      } else {
        sum = sumarray[i] - sumarray[j];
      }
      if (sum > maxSum) {
        maxSum = sum;
      }
    }
  }
  return maxSum;
}

那么时间复杂度是：

  • 构建累加数列，O(n)，n是数组长度。
  • 求最大值，1 + 2 + … + n = O(n2)

解法2

换个思路：

  • 记录两个数字：maxSum（最大sum值），prevSum（当前下标之前元素里的sum值）
  • 遍历这个数组，如果prevSum + array[curr] > array[curr]，那么prevSum += array[curr]；否则 prevSum = array[curr]。
  • 同时判断，prevSum 和 maxSum的大小。

举例：

 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

Round 1
maxSum = 2, prevSum = 2
    v
2, -8, 3, -2, 4, -10
因为 -8 + 2 = -6 > -8，所以 prevSum = -6

Round 2
maxSum = 2, prevSum = -6
       v
2, -8, 3, -2, 4, -10
因为 -6 + 3 = -3 < 3，所以 prevSum = 3，所以 maxSum = 3

Round 3
maxSum = 3, prevSum = 3
           v
2, -8, 3, -2, 4, -10
因为 3 + (-2) = 1 > -2，所以 prevSum = 1

Round 4
maxSum = 3, prevSum = 1
              v
2, -8, 3, -2, 4, -10
因为 1 + 4 = 5 > 4，所以 prevSum = 5，所以 maxSum = 5

Round 5
maxSum = 5, prevSum = 5
                   v
2, -8, 3, -2, 4, -10
因为 5 + (-10) = -5 > -10，所以 prevSum = -5

这个方法的意思是，如果之前的sum加上当前数字对当前情况有提升，那么就将其相加。否则的话还不如直接用当前数字。然后在过程中取得最大的sum。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int maxContiguous(int[] array) {
  int maxSum = array[0];
  int prevSum = array[0];
  for (int i = 1; i < array.length; i++) {
    if (prevSum + array[i] > array[i]) {
      prevSum += array[i];
    } else {
      prevSum = array[i];
    }
    if (prevSum > maxSum) {
      maxSum = prevSum;
    }
  }
  return maxSum;
}

时间复杂度：O(n)

Cracking Coding Interview - 16.16 Sub Sort
Cracking Coding Interview - 16.18 Pattern Matching

版权

CC BY-NC-ND 4.0

相关文章

评论