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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s