對於每個k = 1的所有大小爲k的子陣列的最大總和爲n .. n

給定大小爲n的數組對於從1到n的每個k，求大小k的連續子數組的最大總和。對於每個k = 1的所有大小爲k的子陣列的最大總和爲n .. n

此問題具有時間複雜度O（N ）和O（1）空間的明顯解決方案。 Lua代碼：

array = {7, 1, 3, 1, 4, 5, 1, 3, 6} 
n = #array 

function maxArray(k) 
    ksum = 0 
    for i = 1, k do 
     ksum = ksum + array[i] 
    end 
    max_ksum = ksum 
    for i = k + 1, n do 
     add_index = i 
     sub_index = i - k 
     ksum = ksum + array[add_index] - array[sub_index] 
     max_ksum = math.max(ksum, max_ksum) 
    end 
    return max_ksum 
end 

for k = 1, n do 
    print(k, maxArray(k)) 
end

是否有任何算法具有較低的時間複雜度？例如，O（N log N）+附加內存。

相關信息：

Kadane's algorithm

來源

2015-06-01 starius

-2

下面的過程可能會幫助你

1）選擇第一k個元素，並創建大小爲k的平衡樹（BST）。

2）運行一個循環，其中i = 0到n - K

... ..A）從BST得到最大的元件，並打印。

... ..b）在BST中搜索arr [i]並從BST中刪除它。

... ..c）將arr [i + k]插入BST。

時間複雜度：時間步驟1的複雜度爲O（kLogk）。時間步驟2（a），2（b）和2（c）的複雜度爲O（Logk）。由於步驟2（a），2（b）和2（c）處於運行n-k + 1次的循環中，因此完整算法的時間複雜度爲O（kLogk +（nk + 1）* Logk）也可以寫成O（nLogk）。

來源

2015-06-01 09:50:16

對於每個'k = 1，....，n'，這是'O（n^2logn）'。低於OP的解決方案。使用滑動窗口在O（n）中完成k個相鄰元素的最高總和。不需要'O（nlogk）'樹解決方案。 – amit

-1。我可以解決O（N）中固定k的子問題。問題的關鍵在於對於從1到n **的每個k，需要最大總和的k-子陣列**。 – starius

如果您不添加任何其他約束，我認爲沒有比O（N²）更高效的解決方案。換句話說，沒有其他方法可以決定你找到了最大和子數組，而是去探索所有其他的子數組。

因此，至少絡合物溶液包含O（N²/ 2），它是給定長度N的陣列的子陣列鄰接

我個人將與動態規劃方法實現此的總數量。這個想法是有一個部分結果的楔子，並使用它們來構建子陣列的當前總和（代替通過計算總和）。無論如何，這隻給「恆定」加速，因此複雜度爲O（N 2/2）〜O（N 2）。

以下是僞代碼 - 抱歉，沒有說話的Lua

// here we place temporary results, row by row alternating in 0 or 1 
int[2][N] sum_array_buffer 
// stores the start of the max subarray 
int[N] max_subarray_start 
// stores the value 
int[N] max_subarray_value 

array = {7, 1, 3, 1, 4, 5, 1, 3, 6} 
// we initialize the buffer with the array (ideally 1-length subarrays) 
sum_array_buffer[1] = array 
// the length of subarrays - we can also start from 1 if considered 
for k = 1 ; k <= (N); ++k: 
    // the starting position fo the sub-array 
    for j = 0; j < (N-k+1); ++j: 
     sum_array_buffer[k%2][j] = sum_array_buffer[(k+1)%2][j] + array[j+k-1] 
     if j == 0 || sum_array_buffer[k%2][j] > max_subarray_value[k]: 
      max_subarray_value = sum_array_buffer[k%2][j] 
      max_subarray_start[k] = j 


for k = 1 ; k <= (N); ++k: 
    print(k, max_subarray_value[k])

Graphycally：

來源

2018-01-24 22:37:59

我們創造能力k的出列，齊，只存儲當前窗口的有用元素k元素。如果一個元素位於當前窗口中並且大於當前窗口中左側的所有其他元素，則該元素很有用。我們逐個處理所有數組元素，並保持Qi包含當前窗口的有用元素，這些有用元素按排序順序維護。 Qi前方的元素最大，Qi後方的元素是當前窗口中最小的元素。

來源

2018-02-02 18:29:36 user5811614

對於每個k = 1的所有大小爲k的子陣列的最大總和爲n .. n

回答

相關問題