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] - >這形成了最大總和的連續子陣列。對於不必要的元素組的最大總和，只需添加所有正元素即可。