Answer:
Here is the C++ program:
#include<iostream> //to use input output functions
using namespace std; // to identify objects cin cout
int CountSubArrays(int arr[], int size){ /*function that an array and the size of array as parameters and returns the number of ways it can be split into three non-empty contiguous subarrays such that the sum of the elements in the first subarray is less than or equal to the sum of the elements in the second subarray, and the sum of the elements in the second subarray is less than or equal to the sum of the elements in the third subarray */
int previous[size]; //stores the sum of previous elements
previous[0] = arr[0]; //sets the first element of previous array to first element of arr
for(int i = 1; i < size; i++) //iterates through the array
previous[i] = previous[i - 1] + arr[i]; //adds the present element i-th element of arr to the previous element of previous array
int next[size]; //to store the sum of next elements
next[size - 1] = arr[size - 1]; //sets the last element of previous array to last element of arr
for(int i = size ; i >= 0; i--) //iterates through the array
next[i] = next[i + 1] + arr[i]; //adds the present element i-th element of arr to the next element of next array
int i = 1, j = 1; //sets two variable to move through the array
int current = 0, count = 0;
while (i < size - 1 && j < size - 1) { //moves through the array
while (j < size - 1 && current <=previous[i - 1]) { // updates current array until it is less than previous[i - 1]
current += arr[j++]; } //adds value of current to j-th+1 value of arr
if (current <= next[j]) { //if value of current is less than or equal to the j-th value of next
count++; } //adds 1 to the count and count stores number of ways array can be split
current -= arr[i++]; } //decrements current by arr[i++]
return count; } //returns the number of ways arr can be split into three non-empty contiguous subarrays
int main() { //start of main function
int arr[] = {1,2,2,2,5,0}; //declares and assigns values to array arr
int size = sizeof arr / sizeof arr[0]; //computes the size of array arr
cout << (CountSubArrays(arr, size)); } //calls method by passing arr and size to it in order to find the number of ways it can be split into three non-empty contiguous subarrays
Step-by-step explanation:
The program generates the previous array sum by adding the present element i-th element of arr to the previous element of previous array
It then generates the next array sum by adding the present element i-th element of arr to the next element of next array
Then two pointers i and j are declared in order to find the sum of the second subarray.
Then while loop iterates over the array, increments current array with arr[j++] and this loop continues to execute as long as current stays less than previous[i – 1] .
When the current array is greater than or equal to previous[i – 1], then the if condition checks if current array is less than or equal to next[j]. This part basically works for the condition that the sum of the elements in the first subarray is less than or equal to the sum of the elements in the second subarray, and the sum of the elements in the second subarray is less than or equal to the sum of the elements in the third subarray. The value of count is incremented to 1 when the if statement evaluates to true.
Now the current array is decremented by arr[i+1]
The program repeats the above steps and then the function returns the computed value of count.
The output of the program is attached.