Kadane Algorithim

Kadane-Algorithim

这是著名的动态编程Algo Kadane的Algorithim之一的JavaScript解决方案。

问题陈述

给定一个数组a = {a1，a2，…，n elements的an}，找到一个最大可能的总和

连续的子阵列不连续（不一定是连续）子阵列。
不应考虑空的子阵列/子序列。

本·赖特（Ben Wright）的这部YouTube视频可能很有用，可以理解1D序列中最大子阵列的Kadane算法。

输入格式

输入的第一行具有一个整数T。t情况以下。每个测试用例始于整数N。在下一行中，n个整数遵循表示数组A的元素。

约束：

1≤t≤10
1≤n≤105
-104≤AI≤104

您认为的子阵列和子序列应该至少具有一个元素。

输出格式

两个，空间分开的整数表示最大连续和不连续的子阵列。至少应该选择一个整数并放入子阵列（在所有元素均为负的情况下可能需要这）。

样品输入

2
4
1 2 3 4
6
2 -1 2 3 4 -5

样本输出

10 10
10 11

解释

在第一种情况下：连续和非连续元素的最大总和是所有元素的总和（因为它们都是正面的）。

在第二种情况下：[2 -1 2 3 4] - >这形成了最大总和的连续子阵列。对于不必要的元素组的最大总和，只需添加所有正元素即可。