title: How to find a subarray with minimum k length and maximum sum?
body: <p>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.</p>
  
  <p>Here is my code in c++ using Kadane's algorithm.</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  using namespace std;
  
  int main(){
  
      int n,k;
      cin &gt;&gt; n &gt;&gt; k;
      int array[n];
      int sum = 0;
      int maxsum = 0;
      int beststarts[n];
  
      for(int i = 0;i &lt; n; i++){
              cin &gt;&gt; array[i];
      }
  
      for(int i = 0;i &lt; k-1;i ++){
              sum = sum+array[i];
              beststarts[i] = 0;
      }
  
  
      for(int i =  k-1;i &lt; n; i++){ //best end search with min length;
              sum = sum+array[i];
              int testsum = sum;
              if(i &gt; 0){
              beststarts[i] = beststarts[i-1];
              }
              for(int j = beststarts[i] ;i-j &gt; k-1;j ++){
                      testsum = testsum - array[j];
                      if(testsum &gt; sum){
                              beststarts[i] = j+1;
                              sum = testsum;
                      }
              }
              if(sum &gt; maxsum){
                      maxsum = sum;
              }
      }
  
      cout &lt;&lt; maxsum;
  
      return 0;
  }
  </code></pre>
  
  <p>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 <a href="https://stackoverflow.com/questions/13089010/arraysfind-longest-subarray-whose-sum-divisible-by-k">Find longest subarray whose sum divisible by K</a> but that is not what i want, the length can be greater than k also.</p>