数组（至少包含一个数字）中具有最大总和的连续子数组
下面的代码实现了O（n^2）的时间复杂度。我希望能够在O（n）中完成。
例如，给定阵列[-2，1，-3，4，-1，2，1，-5，4]，连续子阵列[4，-1，2，1]具有最大和= 6。
def maximum_sub_array(arr, n):
ans = - sys.maxint - 1
for start_index in range(0, n):
_sum = 0
for sub_array_size in range(1,n+1):
if (start_index + sub_array_size > n): # Subarray exceeds array bounds
break
_sum += arr[start_index + sub_array_size -1] # Last element of the new Subarray
ans = max(ans, _sum)
return ans
共有1个答案
熟悉卡丹的算法。实现的时间复杂度为 O（n）。
def Maximum_Sub_Array(arr, n):
ans = 0
_sum = 0
num_of_neg_values = 0
for i in range(n):
if arr[i] < 0:
num_of_neg_values += 1
if (_sum + arr[i] > 0):
_sum += arr[i]
else:
_sum = 0
ans = max(_sum, ans)
if num_of_neg_values == n:
return max(arr)
return ans
-
我在一次采访中被问到这个问题。给定一个整数数组（具有正值和负值），我们需要找到具有相等总和的不相交子数组的最大数量。 例子： 输入：[1,2,3]输出：2{因为我们最多有2个子数组，总和=3，即[1,2]，[3]} 输入： [2 2 2 -2] 输出 ： 2 {两个子数组，每个子数组的总和 = 2，即 [2]，[2， 2， -2]} 我的方法 我想到的第一种方法是找到前缀和数组，然后以每个元素（前
-
你是一个电视游戏节目的参与者，这给了你赢得奖金的机会。在游戏中，你会看到一系列框，每个框都包含一个允许你看到的正整数值。你有机会选择任何数量的盒子。您的总奖金是您选择包含的所有盒子的总和。这个游戏只有一个限制：如果你选择了两个连续的盒子，你不允许在总数中添加任何后续的盒子，而你的奖品是截至该点的累计金额。你的目标是最大化你的奖金。 给定一个正整数数组，代表游戏中呈现给你的每个盒子的值，返回你能赢得
-
NowCoder 题目描述 {6, -3, -2, 7, -15, 1, 2, 2}，连续子数组的最大和为 8（从第 0 个开始，到第 3 个为止）。 解题思路 // java public int FindGreatestSumOfSubArray(int[] nums) { if (nums == null || nums.length == 0) return 0;
-
本文向大家介绍求一个数组中连续子向量的最大和相关面试题，主要包含被问及求一个数组中连续子向量的最大和时的应答技巧和注意事项，需要的朋友参考一下 考察点：数组
-
一、题目 输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。 例子说明： 例如输入的数组为{1, -2, 3, 10, -4, 7, 2, -5}，和最大的子数组为｛3, 10, -4, 7, 2}。因此输出为该子数组的和18 。 二、解题思路 解法一：举例分析数组的规律。 我们试着从头到尾逐个累加示例数组中的每个
-
题目描述 输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值，要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2， 因此输出为该子数组的和18。 分析与解法 解法一 求一个数组的最大子数组和，我想最直观最野蛮的办法便是，三个f