Scribd
Upload
24 views5 pages

Coding Question Template

The document outlines a problem where an array of integers must be divided into three continuous subarrays with the first and third segments having the same sum, while maximizing this sum. It provides input and output formats, sample inputs with their corresponding outputs, and a solution in C. The solution involves calculating prefix and suffix sums to find the optimal segments.

Uploaded by

raikaushal5033
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
24 views5 pages

Coding Question Template

The document outlines a problem where an array of integers must be divided into three continuous subarrays with the first and third segments having the same sum, while maximizing this sum. It provides input and output formats, sample inputs with their corresponding outputs, and a solution in C. The solution involves calculating prefix and suffix sums to find the optimal segments.

Uploaded by

raikaushal5033
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Balance Array Segments

Level of Difficulty: Medium

Concept Tags: Prefix Sum, Two Pointers, Arrays, Sliding Window

Background:
[You’re working with a system that processes time-series data divided into segments. To
optimize storage and improve analysis accuracy, it's crucial to identify balanced chunks in
the data where the starting and ending segments have identical total values.

Objective:
Given an array of integers, divide it into three continuous subarrays (segments), where the
first and third segments must have the same sum, and the goal is to maximize this common
sum. The middle segment can be of any length (including zero), and empty subarrays are
also allowed.

Input Format:
- The first line contains an integer `N` — the number of elements in the array.
- The second line contains `N` space-separated integers — the values in the array.

Output Format:
- Print a single integer: the maximum sum of the first and third subarrays such that they are
equal.

Constraints:
1 ≤ N ≤ 2 × 10⁵
1 ≤ arr[i] ≤ 10⁹
Sample Input and Output:

Sample Input 1:
5
13114

Sample Output 1:
5

Explanation 1:
The optimal division is:

 First Segment: [1, 3, 1] → sum = 5

 Second Segment: []

 Third Segment: [1, 4] → sum = 5

Sample Input 2:
5

13214

Sample Output 2:
4

Explanation 2:
A valid split is:

 First Segment: [1, 3] → sum = 4

 Second Segment: [2, 1]

 Third Segment: [4] → sum = 4

Sample Input 3:
3

412

Sample Output 3:
0

Explanation 3:
There is no non-zero sum possible where the first and third segments have the same sum.
So, the answer is 0 (with empty first and third segments).

Solution < C, Java or Python> :

#include <stdio.h>

#define MAXN 200005

typedef long long ll;

int main() {

int n;

scanf("%d", &n);

int arr[MAXN];

ll prefix[MAXN] = {0};

ll suffix[MAXN] = {0};

for (int i = 0; i < n; i++) {

scanf("%d", &arr[i]);

// Build prefix sum

for (int i = 0; i < n; i++) {

prefix[i + 1] = prefix[i] + arr[i];


}

// Build suffix sum

suffix[n] = 0;

for (int i = n - 1; i >= 0; i--) {

suffix[i] = suffix[i + 1] + arr[i];

ll result = 0;

int left = 0;

int right = n;

while (left <= right) {

if (prefix[left] == suffix[right]) {

result = prefix[left];

left++;

right--;

} else if (prefix[left] < suffix[right]) {

left++;

} else {

right--;

printf("%lld\n", result);

return 0;
}

Backend Test Cases < 3 easy, 4 medium, 3 difficult>:

 n = 7, arr = [1, 2, 3, 4, 3, 2, 1] → Output: 6

 n = 5, arr = [4, 1, 0, 1, 4] → Output: 5

 n = 10^5, all elements = 1 → Output: 50000

 n = 10^5, arr = [1 to 10^5] increasing → Output: 0

You might also like