Maximum Sum with atleast k elements

Maximum Sum with atleast k elements

  October 19, 2017    

---

Idea is to first use algo to find max sum till ith position and save them.
then check for 2 elements sum
Check max from 2 sum and sum+max_sum[i-k]

Code:

static int maxSumWithatleastK(int a[], int n, int k)
{
int sum=a[0];
int max_sum[]=new int[n];
max_sum[0]=a[0];
for(int i=1;i<n;++i)
{
max_sum[i]=Math.max(max_sum[i-1]+a[i],a[i]);
}
for(int i=1;i<k;++i)
{
sum+=a[i];
}
int result=sum;
for(int i=k;i<n;++i)
{
sum=sum+a[i]-a[i-k];
result=Math.max(result,Math.max(sum,sum+max_sum[i-k]));
}
return result;
}