Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Arrays

Array Max

Prepbytes

CONCEPTS USED:

Suffix Sum Arrays

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Given an array of N integers and an integer K, the task is to find the maximum sum taking every Kth element i.e.

sum = arr[i] + arr[i + k] + arr[i + 2 *k] + arr[i+ 3 * k] + … arr[i+ q * k]

starting with any i value.

NOTE:

  1. He can stop moving to (i+k)th index at any time he wishes.

  2. Minimum value that sum can have is zero, it should never become negative throughout the calculation.

For Example:

Input : N = 5, K = 2
        A[] = [1, 2, 3, 4, 5]

Output : 9

Explanation : Start with index = 0 and sum = 0

sum = sum + A[0] = 0 + 1 = 1
i = i + 2 = 0 + 2 = 2

sum = sum + A[2] = 2 + 3 = 5
i = i + 2 = 2 + 2 = 4

sum = sum + A[4] = 4 + 5 = 9
i = i + 2 = 4 + 2 = 6

Similarly starting from other indexes and finding sum values, we obtain that
9 is the maximum sum that can be obtained.

BRUTEFORCE METHOD:

  1. Begin with choosing a starting index(i = 0), adding value at this index to the sum, comparing sum with max value and updating max value. Keep taking K steps and updating max value till i becomes equal to N`.

  2. Follow Step-1 for all such indexes and finally find the maximum sum out of all such sum values.

  3. Time Complexity of this solution is O(N2) as we will be running two nested loops.

SOLUTIONS:

#include 

int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n,k;
    scanf("%d %d",&n,&k);
    int arr[n];
    for(int i=0;imax_val)
          max_val = sum;
        j += k;
      }
    }
    printf("%d\n",max_val);
  }

  return 0;
}




#include 
using namespace std;

int main()
{
  int t;cin>>t;
  while(t--)
  {
    int n,k;cin>>n>>k;
    int arr[n];
    for(int i=0;i>arr[i];
    int max_val = 0;
    int sum = 0;
    for(int i=0;i
						 
import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t!=0)
    {
      int n = sc.nextInt();
      int k = sc.nextInt();
      int arr[] = new int[n];
      for(int i=0;imax_val)
            max_val = sum;
          j += k;
        }
      }
      System.out.println(max_val);
      t--;
    }   
  }
}

EFFICIENT METHOD:

  1. It can be solved by using the concept of Suffix Sum Arrays where we start iterating the array from right side and keep storing the suffix sum for each (i+k)th element where (i+k)<n.

  2. Finally we find the maximum sum from the Suffix Sum Array.

What are Suffix Sum Arrays?

Suffix Sum Arrays are of same size of the normal array such that the ith index of this array stores the sum of values from ith index value to the last value of the original array i.e.

SuffixArray[i] = A[i] + A[i+1] + .... + A[N-1]

SOLUTIONS:

#include 

int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n,k;
    scanf("%d %d",&n,&k);
    int arr[n];
    for(int i=0;i=0;i--)
    {
      if(i+k < n)
      {
        if(arr[i]+sum[i+k]<0)
          sum[i] = 0;
        else
          sum[i] = arr[i]+sum[i+k];
      }
      else
      {
        if(arr[i]<0)
          sum[i] = 0;
        else
          sum[i] = arr[i];
      }
      if(sum[i]>max_val)
        max_val = sum[i];
    }
    printf("%d\n",max_val);
  }

  return 0;
}




#include 
using namespace std;

int main()
{
  int t;cin>>t;
  while(t--)
  {
    int n,k;cin>>n>>k;
    int arr[n];
    for(int i=0;i>arr[i];
    }

    int max_val = 0;
    int sum[n];
    for(int i=0;i=0;i--)
    {
      if(i+k < n)
      {
        if(arr[i]+sum[i+k]<0)
          sum[i] = 0;
        else
          sum[i] = arr[i]+sum[i+k];
      }
      else
      {
        if(arr[i]<0)
          sum[i] = 0;
        else
          sum[i] = arr[i];
      }

      max_val = max(max_val,sum[i]);
    }
    cout<
						 
import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t!=0)
    {
      int n = sc.nextInt();
      int k = sc.nextInt();
      int arr[] = new int[n];
      for(int i=0;i=0;i--)
      {
        if(i+k < n)
        {
          if(arr[i]+sum[i+k]<0)
            sum[i] = 0;
          else
            sum[i] = arr[i]+sum[i+k];
        }
        else
        {
          if(arr[i]<0)
            sum[i] = 0;
          else
            sum[i] = arr[i];
        }
        if(sum[i]>max_val)
          max_val = sum[i];
      }
      System.out.println(max_val);
      t--;
    }  
  }
}

Leave a Reply

Close

Related Post