# Max Sum K – Partition

Agarwal has a habit of creating Ajeeb Samasya as usual and Shubham always comes to his rescue. This is time he has created another samasya which is as follows. Read carefully! Shubham has an array of N integers and an integer K. He wants to create a subsequence of this array with some conditions applied. He builds ceil(N/K) blocks of this array with size of each block as [i∗K+1,min((i+1)∗k,N)] for 0≤i≤N/K. For two consecutive integers in this subsequence, he wants the integers to be of two different blocks. (It is not a compulsion to have one integer from each block). Also, lets say the indexes of any two integers of this subsequence be i and j, then he wants |i−j| != K. Shubham takes the sum of integers in the subsequence. He wonders what can be the maximum sum obtained? Help shubham in this samasya.

Input Format

First line contains two space separated integers : N and K Second line contains N space separated integers : A1, A2,…, AN

Output Format

print a single integer describing maximum sum that can be obtained.

Sample Input

``````6 5
5 4 3 2 1 -1``````

Sample Output

``5``

## Solution

```import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int k = scan.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++)
arr[i] = scan.nextInt();
long prevBestSum = 0, prevBestIndex = Integer.MIN_VALUE, prevSecSum = 0;
long curBestSum = 0, curBestIndex = Integer.MIN_VALUE, curSecSum = 0;
long sum = 0;
int len = (n + k - 1)/k;
for(int i=0;i<len;i++)
{
for(int j=i*k;j<(i+1)*k&&j<arr.length;j++)
{
if(j - prevBestIndex != k)
{
sum = prevBestSum + arr[j];
}
else
{
sum = prevSecSum + arr[j];
}
if(curBestSum < sum)
{
curSecSum = curBestSum;
curBestSum = sum;
curBestIndex = j;
}
else if(curSecSum < sum)
curSecSum = sum;
}
prevBestSum = curBestSum;
prevBestIndex = curBestIndex;
prevSecSum = curSecSum;
}
System.out.println(curBestSum);
}
}
```

## Code Walkthrough

``````n = 6;
k = 2;

arr = {5, 4, 3, 2, 1, -1}

prevBestSum = 0;
prevBestIndex = 0;
prevSecSum = 0;

len = (n+k-1)/k ==> (6 + 2 - 1)/2 ==> 3

curBestSum = 0;
curBestIndex = 0;
curSecSum = 0;

i = 0,1,2
j = i*k => 0,2,4

j < (i+1)*k => 2,4,6

Calculate Sum
arr = {5, 4, 3, 2, 1, -1}

At i = 0,
for(int j = i*k; j < (i+1)*k; j++)
{
//j runs 0,1
if(j - prevBestIndex != k)
sum = prevBestSum + a[j];
else
sum = prevSecSum + a[j];

if(sum > curBestSum)
{
curSecSum = curBestSum;
curBestSum = sum;
curBestIndex = j;
}
else if(sum > curSecSum)
{
curSecSum = sum;
}

prevBestSum = curBestSum;
prevBestIndex = curBestIndex;
prevSecSum = curSecSum;
}
``````