如何找到一个具有最小k长度和最大总和的子阵列? [英] How to find a subarray with minimum k length and maximum sum?
本文介绍了如何找到一个具有最小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
这篇关于如何找到一个具有最小k长度和最大总和的子阵列?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文