最大总和连续子数组
给出了一个整数数组。我们必须找到所有元素的总和，这些元素的总和最大，这些元素将作为输出发送。
使用动态编程，我们将存储当前项的最大和。这将有助于找到数组中连续元素的总和。
输入输出
Input:
An array of integers. {-2, -3, 4, -1, -2, 1, 5, -3}
Output:
Maximum Sum of the Subarray is: 7
算法
maxSum(array, n)
输入-主数组，数组的大小。
输出-最大和。
Begin tempMax := array[0] currentMax = tempMax for i := 1 to n-1, do currentMax = maximum of (array[i] and currentMax+array[i]) tempMax = maximum of (currentMax and tempMax) done return tempMax End
示例
#include<iostream>
using namespace std;
int maxSum( int arr[], int n) {
int tempMax = arr[0];
int currentMax = tempMax;
for (int i = 1; i < n; i++ ) { //find the max value
currentMax = max(arr[i], currentMax+arr[i]);
tempMax = max(tempMax, currentMax);
}
return tempMax;
}
int main() {
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = 8;
cout << "Maximum Sum of the Sub-array is: "<< maxSum( arr, n );
}
输出结果
Maximum Sum of the Sub-array is: 7
-
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
-
本文向大家介绍求一个数组中连续子向量的最大和相关面试题，主要包含被问及求一个数组中连续子向量的最大和时的应答技巧和注意事项，需要的朋友参考一下 考察点：数组
-
下面的代码实现了O（n^2）的时间复杂度。我希望能够在O（n）中完成。 例如，给定阵列[-2，1，-3，4，-1，2，1，-5，4]，连续子阵列[4，-1，2，1]具有最大和= 6。
-
你是一个电视游戏节目的参与者，这给了你赢得奖金的机会。在游戏中，你会看到一系列框，每个框都包含一个允许你看到的正整数值。你有机会选择任何数量的盒子。您的总奖金是您选择包含的所有盒子的总和。这个游戏只有一个限制：如果你选择了两个连续的盒子，你不允许在总数中添加任何后续的盒子，而你的奖品是截至该点的累计金额。你的目标是最大化你的奖金。 给定一个正整数数组，代表游戏中呈现给你的每个盒子的值，返回你能赢得
-
我在一次采访中被问到这个问题。给定一个整数数组（具有正值和负值），我们需要找到具有相等总和的不相交子数组的最大数量。 例子： 输入：[1,2,3]输出：2{因为我们最多有2个子数组，总和=3，即[1,2]，[3]} 输入： [2 2 2 -2] 输出 ： 2 {两个子数组，每个子数组的总和 = 2，即 [2]，[2， 2， -2]} 我的方法 我想到的第一种方法是找到前缀和数组，然后以每个元素（前
-
我试图在一个数组中找到具有最大和的邻接子数组。所以，对于数组 {5,15,-30,10,-5,40,10}