如何找到一个具有最小k长度和最大总和的子阵列？

本文介绍了如何找到一个具有最小k长度和最大总和的子阵列？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

子阵列包含正数和负数。你必须找到一个最大和的子阵列，以使子数组的长度大于或等于k。

The subarray contains both positive and negative numbers. You have to find a maximum sum subarray such that the length of the sub-array is greater than or equal to k.

这是我的代码在c ++使用Kadane的算法。

Here is my code in c++ using Kadane's algorithm.

#include <iostream> using namespace std; int main(){ int n,k; cin >> n >> k; int array[n]; int sum = 0; int maxsum = 0; int beststarts[n]; for(int i = 0;i < n; i++){ cin >> array[i]; } for(int i = 0;i < k-1;i ++){ sum = sum+array[i]; beststarts[i] = 0; } for(int i = k-1;i < n; i++){ //best end search with min length; sum = sum+array[i]; int testsum = sum; if(i > 0){ beststarts[i] = beststarts[i-1]; } for(int j = beststarts[i] ;i-j > k-1;j ++){ testsum = testsum - array[j]; if(testsum > sum){ beststarts[i] = j+1; sum = testsum; } } if(sum > maxsum){ maxsum = sum; } } cout << maxsum; return 0; }

我的代码工作正常，但很慢，任何方式来提高我的代码。我也读过这个问题 [Arrays]找到最长的子阵列，其和可以除以

My code is working fine but it is very slow, and i cant think of any ways to improve my code. I have also read this question [Arrays]find longest subarray whose sum divisible by K but that is not what i want, the length can be greater than k also.

推荐答案

解决方案基于此答案

即时演示

#include <algorithm> #include <iterator> #include <iostream> #include <numeric> #include <ostream> #include <utility> #include <vector> // __________________________________________________ template<typename RandomAccessIterator> typename std::iterator_traits<RandomAccessIterator>::value_type max_subarr_k(RandomAccessIterator first,RandomAccessIterator last,int k) { using namespace std; typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; if(distance(first,last) < k) return value_type(0); RandomAccessIterator tail=first; first+=k; value_type window=accumulate(tail,first,value_type(0)); value_type max_sum=window, current_sum=window; while(first!=last) { window += (*first)-(*tail) ; current_sum = max( current_sum+(*first), window ); max_sum = max(max_sum,current_sum); ++first; ++tail; } return max_sum; } // __________________________________________________ template<typename E,int N> E *end(E (&arr)[N]) { return arr+N; } int main() { using namespace std; int arr[]={1,2,4,-5,-4,-3,2,1,5,6,-20,1,1,1,1,1}; cout << max_subarr_k(arr,end(arr),4) << endl; cout << max_subarr_k(arr,end(arr),5) << endl; }

输出为：

14 11