# Array Max

#### 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(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]`

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

```