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.

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;
}
```

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.

Solution based on this answer

```
#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;
}
```

Output is:

```
14
11
```

```
int w(0);
for (int i=0; i < k; i++) w += a[i];
int run_sum(w), max_sum(w);
for (int i=k; i < n; i++) {
w = a[i] + max(w, w-a[i-k]); // window will such that it will include run_sum
run_sum = max(run_sum + a[i], w);
max_sum = max(run_sum, max_sum);
}
return max_sum;
```

Similar Questions

I need to find maximum possible sum of numbers in arrays but number must be drawn from a unique array index...just like that: double maxSum = 0; double a = {1.0 , 2.0, 3.0}; double b = {4.0 , 5.0, 6.0

I own a canvas website and want my customers to be able to enter a custom length of the canvas within a set range. Say the range for the product is: Minimum: 10 cm Maximum: 200 cm Then in the text

How can I find out the minimum and maximum values of a certain array of Integer ?

I've been working with Binary Search Trees in my spare time, and I want to be able to delete nodes from a tree. In order to get this to work, I need to find the maximum value. How do you go about doin

I'm having problem finding a way to extract the indices of a subarray. The problem: find the subarray with the max value from one original array. My solution: Finds the right array, but returns the va

How to find minimum and maximum length given a regular expression ? For example [1-9]?[0-9] This regular expression can generate a minimum 1 (0 or 1 0r 2.... or 9) and a maximum of string length 2 (

I need to get minimum and maximum values from different variables. i getting variable values xMin, yMin, xMax and yMax and i need to find minimum xMin value, minimum yMin value, maximum xMax value and

Let's say I have two strings: hello love The size of the maximum subarray in the strings is 2: lo. Here's another example: ABBABBA BBABCBA Maximum subarray: BBAB Size: 4 Basically, how c

Suppose you have a K dollars Bill. Given 4 coins of value {1,4,6,9} Find the minimum number of coins the sum of which is K, when K is represented in Binary, meaning input's length is log(K) I've tried

I am developing an asp.net application where i have a dataset having 3 tables i.e. ds.Tables[0], Tables[1] and Tables[2] I need to find minimum number and maximum number out of all the 3 tables of dat

I have the following file: T$57 abc string (50.00,110.00) T$97 xyz string (30.00,-1100.00) I need to put (50.00,110.00) , (30.00,-1100.00) in new file and finally saving the maximum number for x-coord

this is the exercise 2.41 in SICP I have wrote this naive version myself: (defn sum-three [n s] (for [i (range n) j (range n) k (range n) :when (and (= s (+ i j k)) (< 1 k j i n))] [i j k])) The q

This question already has an answer here: How to use LINQ to select object with minimum or maximum property value 5 answers I have a class A { public float Score; ... } and an IEnumerable<A&

I have the following Regex expression for java application: [\+0-9]+([\s0-9]+)? How to restrict the above expression of telephone number to a minimum of 4 digits and maximum of 7 digits? I thought it

I want to modify Prim's algorithm so that it find the maximum spanning tree how can this be done

I need to know the maximum length of a textbox in ssrs. How much data can it accomodate?

I have 2 textbox one is of Minimum Price and other is of Maximum Price.I want the validation when one enter the Minimumm price greater than Maximum Price that you have enter the Minimum Price greater

Given an Array A of N non negative integers, find an integer k, such that the sum of difference of each element with k is minimum. i.e. Summation(abs(A[i] - k)), 1 <= i <= N, or simply |A[1] - k

A little variation of the standard , Subset Sum Problem , is that we want to find a subset of K size from a set of N size ,which sums upto S . The standard brute force solution for yields a complexit

How can I get the pairwise sum of two equal length tuples? For example if I have (0,-1,7) and (3,4,-7) I would like to have (3,3,0) as answer.

Q: I want to find minimum value in an array so far i have wrote the code with for loop, but i want to do this with threading concept, so how can i write the following code with multithreading? stati

This is a seemingly simple question but I cannot find a simple answer. I want to specify the minimum and maximum for the existing Y axis on the chart. Here's the chart: <Window x:Class=TempDataAna

Given N numbers (positive and negative) and T = number of numbers you can choose, how can you compute the maximum sum of intervals? The first number from an interval is considered to be 0. For example

What is the maximum password length I can use with PHP 5.5 password_hash() ?

How to find increasing subsequence of numbers with maximum sum. I find O(N^2) but I want to know O(N log N). Thanks!

Possible Duplicate: Zero sum SubArray An array contains both positive and negative elements, find the subarray whose sum equals 0. This is an interview question. Unfortunately, I cannot read the a

A simple Lua problem here: how to find the index, or key, of the minimum or maximum number in a given table. math.max/math.min only gives the actual max or min number, not the key.

The xaxis in my flot line charts can take an array of data up to but no more than 16 in length. The problem is when my data is less than 16, the x axis is spreading out to show the maximum value of wh

I have the following in my user.rb: validates :fname, :length => { :minimum => 1, :maximum => 100 } validates :lname, :length => { :minimum => 1, :maximum => 100 } How can I update

find longest subarray whose sum divisible by K. It is possible in O(n)? If not can it be done in better then n^2 ?

I want to create an IF Statement that validates whether an input number in a textbox is 0 to 100 only. For example: NumericUpDown num = new NumericUpDown(); num.Maximum = 100; num.Minimum = 0; if (in

Is having both :presence=>true and length validation on my rails model redundant? Or is there a reason to have both?

I encounter maximum length exceeded error when I try to upload a document which is 9MB in size. I know that the issue will be solved if httpRuntime maxRequestLength and requestLengthDiskThreshold in

Given: array of integers value K,M Question: Find the maximum sum which we can obtain from all K element subsets of given array such that sum is less than value M? is there a non dynamic programming s

from itertools import combinations a = [1,2,3] combinations(a,2) #will give me ((1,2),(1,3),(2,3)) combinations(a,3) #will give me ((1,2,3),) but what if I want results of different length which is i

I'm searching for Python code for maximum weight / minimum cost matching in a bipartite graph. I've been using the general case max weight matching code in NetworkX, but am finding it too slow for my

Actually it is the problem #10 of chapter 8 of Programming Pearls 2nd edition. It asked two questions: given an array A[] of integers(positive and nonpositive), how can you find a continuous subarray

I've had a look around, once again and can't find how to set the minimum and maximum dates allowed to be selected on a calendar in ASP.net with VB. I'm using Visual Studio 2010 and it's just a regular

How to find the maximum and minimum value in an array without using if statement.Are there any built in function in to do so in c++? If not is insertion sort the only way?Thanks in advance.

What are the maximum and minimum values, in pixels, for the CSS background-position property? More precisely, if we use background-position: xpos ypos; where xpos and ypos are pixels, what is the all

One of my friends was asked this question recently: You have to count how many binary strings are possible of length K. Constraint: Every 0 has a 1 in its immediate left.

I'd like to create a function that will print the sum and the position of the maximum value within a list of numbers, but I'm not sure how to go about doing so.. This is what I've started with so far:

Possible Duplicate: What is the maximum length of an url? What is max number of Query Arguments supported in the GET Request and in total how long can this GET request be? Similarly for POST Request

I'm having problems grasping why my function that finds maximum and minimum in a range of doubles using CUBLAS doesn't work properly. The code is as follows: void findMaxAndMinGPU(double* values, int*

I am new to PHP and scripting languages. I am trying to set a slider with the minimum and maximum values for the slider. I want the minimum and maximum values to be displayed even when I move the slid

Possible Duplicate: Getting the submatrix with maximum sum? Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the

What are the maximum lengths for identifiers in BigQuery (names for projects, data sets, tables, columns)? The documentation just says string wherever these identifiers are referenced, but I can't f

I have image zooming and dragging in my application my requirement is the image sets maximum and minimum zooming levels. I have used the below code. public class Touch extends Activity implements OnTo

there is a tree, and the tree is defined as public class TreeNode { int val; vector<TreeNode *> children; TreeNode(int x) { val = x; } } please find the maxmum common subtree(have the most numb

The problem is to color tree vertices with natural numbers such that sum of numbers(colors) assigned to vertices be minimum. Is number of colors to do that bounded?