最大和子数组问题

2024 年 8 月 29 日 | 阅读 12 分钟

在这个问题中，我们将得到一个整数数组，我们需要找到给定数组所有可能子数组中和最大的子数组。

让我们看一个例子来理解这个问题。

输入： 数组 = [-2, -3, 4, -1, -2, 1, 5, -3]

输出 7

这个数组的所有子数组中，最大和是 7。

暴力破解法

解决这个问题的最简单方法是计算给定数组所有可能子数组的和，比较它们，并找到最大的可能和。使用这种方法解决此问题需要 3 个循环。第一个或最外层循环将标记每个子数组的开始。此循环将遍历数组的所有元素。第二个循环将标记子数组的结束。对于每个子数组，结束索引将等于 n - 1，其中 n 是给定数组中元素的数量。最后一个循环将计算由外部两个循环标记的起始索引和结束索引之间每个可能的子数组的和。在计算和的同时，我们将不断检查最大和，因此，最终我们将得到最大的可能子数组和。

以下是我们使用暴力方法解决此问题将遵循的步骤：

首先，我们将启动一个 for 循环，从索引 0 运行到 n - 1。假设此循环的迭代器是 s。s 将是子数组的起始索引。
在第一个循环内部，我们将运行另一个 for 循环来标记子数组的结束。对于每个子数组，结束索引将是 n - 1。假设此循环的迭代器是 e。此循环将从起始到最后一个可能的结束索引运行，因此从 s 到 n - 1。
最后一个或最内层循环将计算每个子数组的和。此循环将从子数组的起始索引 s 运行到结束索引 e。此循环将给出由索引 s 和 e 界定的子数组的和。
完成此循环后，我们将检查此循环的和值是否大于到目前为止的最大和值。如果是，我们将更新最大和值。
最后，我们将返回最大和。

代码

# Python program to use the brute force algorithm to give the value of the maximum sum a subarray can have of the given array

# Defining the function that will take the array and the length of the array and return the maximum sum
def maxSubArraySum(array, n):

  # Initializing the maximum sum value as the minimum sum a subarray can have
  max_sum = -float("inf") - 1 

  # Starting the outermost for loop to mark the starting index of the subarrays
  for s in range(n):

    # Starting the inner for loop to mark the ending of the subarray
    for e in range(s, n):

      # Starting the innermost for loop to calculate the sum of the subarray array[s.....e]
      summ = 0

      # adding all the elements of the subarray s to e
      for i in range(s, e+1):
        summ += array[i]

      # Checking if the sum of the subarray is greater than the max_sum; if yes, then update the max_sum
      max_sum = max(max_sum, summ)

  # Returning the max_sum
  return max_sum

# Creating an array and passing it to the above function
array = [-2, -4, 5, -1, -3, 1, 5, -2]
n = len(array)
print("The maximum sum of a subarray is", maxSubArraySum(array, n))

输出

The maximum sum of a subarray is 7

时间复杂度： 由于我们使用了三个 for 循环，因此此方法的时间复杂度将是立方级的。因此，最终时间复杂度为 O(n^3)，其中 n 是数组中给定的元素数量。

空间复杂度： 我们在此方法中没有使用任何额外的空间；因此，空间复杂度是常数，即 O(1)。

最优方法

立方时间复杂度是暴力方法的主要缺点。然而，我们可以稍微优化此方法，将时间复杂度从立方级降低到二次级。正如我们可以在第三个循环内部观察到的那样，我们正在计算以下子数组的和：array[s : s+1]、array[s : s+2]、array[s : s+3]，依此类推，直到 array[s : e]。因此，我们正在重新计算前一个子数组的和，然后添加当前元素。因为 sum(array[s : s+3]) = sum(array[s : s+1]) + array[s+2]。

以下是我们将遵循的步骤：

我们将像之前的方法一样开始。我们将创建一个 for 循环，它将遍历每个数组元素。此循环的迭代器 s 将标记子数组的开始。
初始化一个变量来存储子数组的和。让它为 summ，且 summ = 0。
然后，我们将启动第二个 for 循环，它将从 s 运行到 n - 1。这将是子数组的结束。
在第二个循环内部，我们不需要添加另一个循环。我们将当前元素添加到和中，即 summ += array[e]。然后，在第二个循环的每次迭代中，我们将更新当前子数组和的 max_sum。

代码

# Python program to use the optimal approach to give the value of the maximum sum a subarray can have of the given array

def maxSubArraySum(array, n):
  
  # Initializing the maximum sum value as the minimum sum a subarray can have
  max_sum = -float("inf") - 1

  # Starting the outermost for loop to mark the starting index of the subarrays
  for s in range(n):
    summ = 0
    # Starting the inner for loop to mark the ending of the subarray
    for e in range(s, n):
      # The current subarray is array[s : e]
      # We will start with the value e = s + 0; the sum will be 0 only as this is an empty array
      # Next, we will go onto e = s + 1; the current element will be an array[s + 1], and we will add this element to the sum of the array[s : s + 0].
      summ += array[e]

      max_sum = max(max_sum, summ)

  # Returning the max_sum
  return max_sum

# Creating an array and passing it to the above function
array = [-2, -4, 5, -1, -3, 1, 5, -2]
n = len(array)
print("The maximum sum of a subarray is", maxSubArraySum(array, n))

输出

The maximum sum of a subarray is 7

Kadane 算法

为了解决这个问题，我们将使用著名的 Kadane 算法。在这个算法中，我们将维护两个变量。第一个变量将存储以任何特定索引结尾的连续子数组的最大和值。我们称之为 max_end_here。第二个变量将存储我们目前遇到的所有单个子数组的最大和。我们称之为 max_till_now。在每次迭代中，我们将检查 max_end_here 的值是否超过 max_till_now 的值。如果是，我们将更新 max_till_now 的值。这样，在循环结束时，我们将得到数组中子数组可能拥有的最大和。

用两句话总结 Kadane 算法：-

我们将忽略和为负数的子数组。我们将通过从零重新开始连续数组的和来做到这一点。也就是说，我们将声明 max_end_here = 0。
我们将继续添加数组的整数，直到和为正数。

忽略和为负数的子数组是因为，例如，数组是 [2, 3, -6, 10, 1]。子数组 [2, 3, -6] 的和为 -1。现在，子数组 [10, 1] 的和为 11。现在很清楚：将子数组 [2, 3, -6] 添加到子数组 [10, 1] 没有任何意义，因为它只会减少和。

所以这是我们的伪代码

1. 初始化变量

max_till_now = -float("inf")

max_end_here = 0

2. 遍历数组中的每个项

(a) max_end_here = max_end_here + array[i]

(b) 如果 (max_till_now < max_end_here)

max_till_now = max_end_here

max_end_here = 0

返回 max_till_now

让我们通过一个例子来理解其功能。我们将在数组 array = [-2, -4, 5, -1, -3, 1, 5, -2] 上进行代码演练。

3. 初始化两个主要变量

max_till_now = -float("inf")

max_end_here = 0

4. 启动循环

对于 i = 0, array[0] = -2

max_end_here = max_end_here + (-2)

将 max_end_here 的值设置为 0，因为 max_end_here < 0

并将 max_till_now 设置为 -2

对于 i=1, array[1] = -4

max_end_here = max_end_here + (-4)

由于 max_end_here < 0 且 max_till_now = -2, max_till_now 将变为 -6

将 max_end_here 的值设置为 0，因为 max_end_here < 0

对于 i = 2, array[2] = 4

max_end_here = max_end_here + (5)

max_end_here = 5

max_till_now 现在设置为 5，因为 max_end_here 的值大于 max_till_now

max_till_now = 5

对于 i = 3, array[3] = -1

max_end_here = max_end_here + (-1)

max_end_here = 4

不改变 max_till_now 的值，因为它大于 max_end_here

对于 i = 4, array[4] = -3

max_end_here = max_end_here + (-3)

max_end_here = 1

对于 i = 5, array[5] = 1

max_end_here = max_end_here + (1)

max_ending_here = 2

对于 i = 6, array[6] = 5

max_end_here = max_end_here + (5)

max_end_here = 7

max_till_now 将现在设置为 7，因为 max_end_here 的值大于 max_till_now

max_till_now = 7

对于 i = 7, array[7] = -2

max_end_here = max_end_here + (-2)

max_end_here = 6

最后，max_till_now 的值就是我们的答案。因此，初始数组子数组的最大和是 7。

以下是我们应遵循的步骤

我们将初始化两个变量 max_till_now = -float("inf") 和 max_end_here = 0。
然后我们将从 0 到 N - 1 索引启动一个 for 循环，对于每个索引 i，我们将执行以下操作：
- 我们将 array[i] 的值添加到 max_end_here。
- 我们将检查 max_end_here 的值是否超过 max_till_now 的值。如果是，我们将更新 max_till_now 的值。
- 如果在本次迭代中 max_end_here 的值 < 0，我们将声明 max_end_here = 0。
最后，我们将返回 max_till_now 的值。

以下是上述算法的 Python 代码。

代码

# Python program to give the value of the maximum sum a subarray can have of the given array

def maxSubArraySum(array, n):

  # Initializing the variables of Kadane's algorithm
  max_till_now = -float("inf")
  max_end_here = 0

  # Starting the for loop to traverse over each array element
  for i in range(0, n):

    # Adding the value of the current element to max_end_here
    max_end_here = max_end_here + array[i]

    # Checking if the value of max_end_here is greater than the value of max_till_now
    if (max_till_now < max_end_here):

      # If yes, then update the value of max_till_now
      max_till_now = max_end_here

    # If the current max_end_here is less than 0, then setting it to zero, hence restarting the subarray
    if max_end_here < 0:
      max_end_here = 0

  # Returning max_till_now
  return max_till_now

# Creating an array and passing it to the above function
array = [-2, -4, 5, -1, -3, 1, 5, -2]
n = len(array)
print("The maximum sum of a subarray is", maxSubArraySum(array, n))

输出

The maximum contiguous sum is 7

时间复杂度： 我们使用线性循环遍历数组元素；因此，时间复杂度为 O(N)。

辅助空间： 除了存储变量之外，我们没有使用任何额外的内存；因此，空间复杂度是常数，即 O(1)。

Kadane 算法的递归函数

Kadane 算法的基本策略是使用“分而治之”。当我们使用递归函数实现此函数时，我们将把数组分解成更小的子数组。然后，我们将递归调用该函数，以找到每个子数组的最大和。最后一步是结合子问题的单个解决方案并找到最终答案。从而找到任何给定数组子数组的最大和。

现在，我们将看到使用递归函数查找任何给定整数数组子数组最大和的算法。

我们将从定义一个以数组作为参数的函数开始。
递归函数中要做的第一件事是指定基本条件。在这种情况下，基本条件是递归函数传递的数组长度为 1。在这种情况下，我们将返回该数组的元素，因为它是唯一可能的最大和。
现在，我们可以开始编写递归语句了。递归状态的首要任务是将提供的数组分成两半。因此，我们将找到当前数组的中间索引。现在，问题被分成两个子问题。
我们将递归调用数组两半的函数，即 array[ : m] 和 array[m : ]。这些函数调用将分别返回这两个数组的子数组的最大可能和。它们将是 left_max 和 right_max。
然后，我们将遍历当前数组的右半部分，并跟踪从中间点开始到每个数组索引结束的每个子数组的和。通过这种方式，我们可以找到跨越中间元素或包含中间元素的数组的最大和。这将是 right_max_sum。
我们将对数组的左半部分重复相同的过程。这次，我们将从中间元素开始循环，直到数组的开头。通过这种方式，我们可以找到子数组的最大和，包括左半部分的中间元素。这将是 left_max_sum。
现在，我们必须返回特定递归状态的最终答案。当前数组的最终答案将是 right_max、left_max 和 cross_max_sum 这三个和值中的最大值（cross_max_sum 是子数组的最大和，它从左半部分的任何索引开始，到当前数组右半部分的任何索引结束。我们可以通过将 left_max_sum 和 right_max_sum 相加来计算此值，分别给我们跨越中间元素的子数组的最大和。）
当递归栈耗尽时，我们将得到最终答案，即给定数组中任何连续子数组的最大和。

以下是上述递归算法实现的 Python 程序

代码

# Python program to give the value of the maximum sum a subarray can have of the given array using a recursive function

# Defining a function to find the maximum sum, the function will take the array and then return the final solution after completing the recursive calls.
def maxSubArraySum(array):

  # Specifying the base condition: If the array has only one element, then return the element of the array as it will be the maximum sum of the subarray of this array
  if len(array) == 1:
    return array[0]

  # Starting the recursive statements
  # We will divide the problem into smaller sub-problems
  n = len(array) // 2

  # Finding the maximum sum of a subarray of the left half of the current array
  left_max = maxSubArraySum(array[ : n])

  # Finding the maximum sum of a subarray of the right half of the current array
  right_max = maxSubArraySum(array[n : ])

  # Finding the maximum sum of the subarray that includes the middle element of the array
  # As then we can combine the two results to find the final answer
  left_half_sum = -float("inf") - 1
  right_half_sum = -float("inf") - 1
  summ = 0

  # Using a for loop to traverse the given array starting from the middle element to len(array) - 1 index
  for i in range(n, len(array)):
    summ += array[i]
    right_half_sum = max(right_half_sum, summ)

  summ = 0
  # Using a for loop to traverse the given array starting from the middle element to the 0th index
  for i in range(n - 1, -1, -1):
    summ += array[i]
    left_half_sum = max(left_half_sum, summ)

  cross_max_sum = left_half_sum + right_half_sum

  # Returning the maximum sum among the max left half sum, max right half sum, and the max cross sum
  return max(cross_max_sum, max( left_max, right_max ))

# Creating an array and passing it to the above function
array = [-2, -4, 5, -1, -3, 1, 5, -2]
print("The maximum sum of a subarray is", maxSubArraySum(array))

输出

The maximum sum of a subarray is 7

下一个主题使用 Python 进行双边滤波

最大和子数组问题

暴力破解法

最优方法

Kadane 算法

Kadane 算法的递归函数

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

最大和子数组问题

暴力破解法

最优方法

Kadane 算法

Kadane 算法的递归函数

相关帖子

使用 Python 进行亚马逊商品价格追踪器

使用 SMOTE 算法和 Near Miss 算法在 Python 中处理不平衡数据

Python 中的强数

Python 程序检查给定数字是否为斐波那契数

Matplotlib 子图中的图例

使用 PyQt5 的计时器应用程序

2023 年使用 Python 的世界级软件 IT 公司

使用 Python 的公司

Python 程序计算字符串对中匹配字符的数量

Python2.x 和 Python3.x 之间的重要区别

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器