kadanes-algorithm

0熱度

1回答

所以我試圖通過HackerRank上的動態規劃跟蹤。問題提示如下。鑑於陣列A = {A1，A2，...，A N}的N個元素的，找到一個毗連子陣列的非連續的（不一定是連續的）子陣列的最大可能的總和。不應考慮空的子陣列/子序列。輸入格式輸入的第一行具有整數Ť。 T個案如下。每個測試用例都以整數N開頭。在下一行中，N整數代表陣列A。約束上：你認爲至少應該有一個元素子陣列和子序列。輸出格

-1熱度

2回答

發現使用JavaScript

我想有效地收集進一步的計算所有子陣列在javascript在O（n）的時間一維數組的所有子陣列。我不知道這是可能的，但似乎對於一個子數組和kadane公式爲O（n），這是比其他方法更有效。但我不確定我如何在每一步中存儲數組。這個quora question類似，對我的僞代碼是不夠的。感謝您的進一步細分。另一個meta link 一個在此動作例如[3,3，9,9，5] [3], [9], [5]

5熱度

2回答

最大產品前綴字符串

以下是從編碼採訪現場稱爲codility演示問題：一個串S的前綴是S的任何前導連續一部分。例如，「c」和「鱈魚「是字符串」可信度「的前綴。爲了簡單起見，我們要求前綴非空。字符串S的前綴P的乘積是P的出現次數乘以P的長度。更確切地說，如果前綴P由K個字符組成並且P在S中恰好出現T次，那麼乘積等於K * T. 例如，S = 「ABABABA」具有以下前綴：「一」，其乘積等於1 * 4 = 4，

1熱度

1回答

解決MaxDouble切片Kadane的算法變化

我試圖通過解決Codality問題來提高我的技能。我達到了這個一個：https://codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/ 我其實理論上百思不得其解：使用Kadane的算法的陣列和存儲和各項指標的。顛倒數組並執行相同操作。通過一次循環兩個結果集來找出兩者之和的最大值。最大值

0熱度

1回答

兩個最大的連續子數組

我目前正在做一個類似於最大連續子數組問題的問題。但是，不是隻找到一個連續的子數組，而是可以找到兩個不重疊的連續子數組。例如對於下面的測試案例，答案是20，因爲我們可以採取一切，但-20。 5 3 -20 4 8 要做到這一點，我實現了下面的代碼： long long n, nums[500500], dp[500500][2][3]; long long best(int numsLef

3熱度

3回答

用最大總和找出連續的子數組

這裏是我的程序，用於從給定數組中找到子數組（連續）的最大總和。使用kadane的算法非常簡單。 #include <iostream> #include <cstdio> using namespace std; int kadane(int a[], int n) { int max_ending_here = a[0], max_till_now = a[0];

8熱度

8回答

找到子陣列的最小絕對總和

有一個包含（正數和負數）整數的數組A。查找（連續）子數組的元素絕對總和最小的，例如： A = [2, -4, 6, -3, 9] |(−4) + 6 + (−3)| = 1 <- minimal absolute sum 我已經通過實施蠻力算法，這是O(N^2)或O(N^3)開始，但它產生正確的結果。但任務規定： complexity: - expected worst-case time

-1熱度

2回答

Kadane算法在Scheme（球拍）

我理解Kadane的算法（數組中所有順序子數組的最大總和）是如何工作在「僞代碼」中的，並且我確信我可以將它作爲在C或C++中的函數。不過，我試圖使用Scheme（球拍;文件擴展名爲.rkt）中的列表來實現它，這是我沒有經驗的。最終的結果我要找的是... Input: (maxsum `(1 4 -2 1)) Output: 5 到目前爲止，我已經開發了兩個輔助功能我也許能夠在maxsum函

5熱度

3回答

最大的連片子陣的總和大小不大於k

例如，我們有 {2,2,-1}, when k = 0, return -1. when k = 3, return 3. ，因爲我們有負數和一個額外的變量k這甚至棘手。 k可以是任何值，否定的，不作任何假設。我不能參考https://en.wikipedia.org/wiki/Maximum_subarray_problem和https://www.youtube.com/watch

3熱度

3回答

最大子數組（Kadane算法） - 尾遞歸

我想在Prolog中實現Kadane's Algorithm。其中一個要求是尾部調用（遞歸）。我嘗試了很多可能性，但沒有成功。這裏是我的代碼： max_sum(L, S) :- S is 0, H is 0, max_sum(L, H, S). max_sum([], S, S). max_sum([X | L], H, S) :- ( H +