logo标签列表

长度不超过k的连续子序列的最大和

dynamic-programmingsub-arraysubsequence
5
我正在尝试修改Kadane算法以解决一个更具体的问题。 "Original Answer"翻译成"最初的回答"。
def max_Sum(arr, length, k):
if length < k:
    print('length of array should be greater than k')

res = 0
for i in range(0, k):
    res += arr[i]

current_sum = res

for i in range(k, n):
    if k == n:
        for j in range(0, k-1):
            res += arr[j]
        current_sum = res
    else:
        current_sum += arr[i] - arr[i-k]
        print(res, current_sum)
        res = max(res, current_sum)

return res

这是解决最大子数组问题的代码。 我想要做的是找到长度最多为K的最大子数组。
示例：我们有一个数组A = [3，-5 1 2，-1 4，-3 1，-2]，并且我们想要找到长度最多为K = 9的最大子数组。 子数组的长度不应限制在K上，如果存在另一个长度L＜K提供更大的总和，则算法应返回sum [: L]。
在本例中，算法将返回0，但实际上应该返回6，即A [2：5]的总和。
5个回答
2
对于那些寻求O(n)答案的人，你可以轻松地将答案适应到CS StackExchange上的这个问题。该答案解决了相同的问题，其中子序列的长度必须在给定范围内为O(n)。对于这个问题，只需将范围设置为[0，k]。
1

好的，一个O(n * K)的解决方案是对每个小于等于K的可能长度使用滑动窗口。我试图修改Kadane来找到一个O(n)的正确解决方案，但我没成功。

def best_array_fixed_k( arr, length, k ):
    total_sum = 0
    best = 0
    for x in xrange( 0, length ):
        total_sum = total_sum + arr[x]
        if x >= k:
            total_sum = total_sum - arr[x - k]
        if x >= k - 1:
            best = max( best, total_sum )
            # this makes sure that we are considering a window with length = k
    return best

def max_sum( arr, length, k):
    best = 0
    for x in xrange( 1, k + 1):
        best = max( best, best_array_for_fixed_k(arr, length, x ) )
    return best
真是我正在寻找的东西！！谢谢你！ - undefined
0

在https://cs.stackexchange.com/a/151327/10147上有一个O(n)的解决方案。

我们可以通过分治法以O(n log n)的复杂度来解决这个问题。考虑数组的左半部分和右半部分：解决方案要么在（1）左半部分独占，（2）右半部分独占，或者（3）左边的后缀与右边的前缀组合。

为了以O(n)的复杂度解决（3），从中间向左迭代，记录每个索引的最高值或总和。然后向右迭代，并在第一次迭代中，使用索引k - l（如果k-l超出范围，则使用最长可能值）记录前缀长度l的值。

对于示例[3,-5, 1, 2,-1, 4,-3, 1,-2] k = 9，我们有：

[3,-5, 1, 2,-1, 4,-3, 1,-2]
 2  2  2  1  0  <---
          --->  4  4  4  4
 ^-----------------------^
     best = 2 + 4 = 10
0

Java解决方案，时间复杂度为：O(n*k)

public static int maxSumforFixedSizeK(int[] arr, int k){

    // Using simple window sliding technique
    int best_sum;
    int curr_sum=0;

    for( int i=0;i<k;i++)
        curr_sum += arr[i];

    best_sum = curr_sum;

    for( int i=k; i<arr.length; i++) {
        curr_sum += (arr[i] - arr[i - k]);
        best_sum = Math.max(best_sum, curr_sum);
    }

    return best_sum;
}

public static int maxSumforSizeAtMostK(int[] arr, int k){
    int best_sum = Integer.MIN_VALUE;

    // Calculate maximum sum for every window size in interval [1,k] 
    for( int i=1; i<=k; i++ )
        best_sum = Math.max( best_sum, maxSumforFixedSizeK(arr, i) );

    return best_sum;
}
0
O(n) 解决方案
long getMaxProfit(vector<int> pnl, int k) {
    int n = pnl.size();
    long maxprofit = 0;
    int i;
    long profit = 0;
    int start = 0;
    for(i=0;i<n;i++) {
        profit += pnl[i];
        if (profit <= 0) {
            profit = 0;
            start = i+1;
        } else {
            maxprofit = max(maxprofit , profit);
            //slide window if it's size is k
            if (i-start+1 == k) {
                //pnl[start] can never be negative because if it is 
                //negative it would have been removed in previous 
                //minimization
                profit -= pnl[start];
                start++;
            }
             //minimize window if it's size is k
            while(pnl[start] <= 0 && start <=i) {
                profit -= pnl[start];
                maxprofit = max(maxprofit , profit);
                start++;
            }
        }
    }
    return maxprofit;
}
根据目前的写法，你的回答不够清晰。请编辑以添加更多细节，帮助他人理解如何解决所提出的问题。你可以在帮助中心找到关于如何撰写好回答的更多信息。 - undefined
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接