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.

See original problem statement here

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(N^2) as we will be running two nested loops.

    SOLUTIONS:

    #include <stdio.h>
    
    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<n;i++)
          scanf("%d",&arr[i]);
        int max_val = 0;
        int sum = 0;
        for(int i=0;i<n;i++)
        {
          sum = 0;
          int j=i;
          while(j<n)
          {
            if(sum+arr[j]<0)
            {
              sum=0;
            }
            else
              sum += arr[j];
            if(sum>max_val)
              max_val = sum;
            j += k;
          }
        }
        printf("%d\n",max_val);
      }
    
      return 0;
    }
    
    
    
    
    #include <bits/stdc++.h>
    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<n;i++)
          cin>>arr[i];
        int max_val = 0;
        int sum = 0;
        for(int i=0;i<n;i++)
        {
          sum = 0;
          int j=i;
          while(j<n)
          {
            if(sum+arr[j]<0)
            {
              sum=0;
            }
            else
              sum += arr[j];
            max_val = max(sum,max_val);
            j += k;
          }
        }
        cout<<max_val<<"\n";
      }
    
      return 0;
    }
    
    
    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<n;i++)
            arr[i] = sc.nextInt();
          int max_val = 0;
          int sum = 0;
          for(int i=0;i<n;i++)
          {
            sum = 0;
            int j=i;
            while(j<n)
            {
              if(sum+arr[j]<0)
              {
                sum=0;
              }
              else
                sum += arr[j];
              if(sum>max_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 by referring some online programming courses.

What are Suffix Sum Arrays?

Suffix Sum Arrays are of same size of the normal array such that the i^{th} 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:

ARRMAX-2

#include <stdio.h>

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<n;i++)
    {
       scanf("%d",&arr[i]);
    }

    int max_val = 0;
    int sum[n];
    for(int i=0;i<n;i++)
      sum[i] = 0;

    for(int i=n-1;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 <bits/stdc++.h>
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<n;i++)
    {
       cin>>arr[i];
    }

    int max_val = 0;
    int sum[n];
    for(int i=0;i<n;i++)
      sum[i] = 0;

    for(int i=n-1;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<<max_val<<"\n";
  }

  return 0;
}

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<n;i++)
      {
         arr[i] = sc.nextInt();
      }
      int max_val = 0;
      int sum[] = new int[n];

      for(int i=n-1;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--;
    }  
  }
}




Previous post Arithmetic Progression
Next post Greater And Least

Leave a Reply

Your email address will not be published. Required fields are marked *