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!

# Array Max

Last Updated on April 1, 2022 by Ria Pathak

### CONCEPTS USED:

Suffix Sum Arrays

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

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

```