对于每个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

回答

相关问题