Problem Link - Table Sum
Problem Statement
You are given a table with 2 rows and N columns. Each cell has an integer in it. The score of such a table is defined as follows: for each column, consider the sum of the two numbers in the column; the maximum of the N numbers so obtained is the score. For example, for the table
7162
1234
the score is max(7 + 1, 1 + 2, 6 + 3, 2 + 4) = 9.
The first row of the table is fixed, and given as input. N possible ways to fill the second row are considered:
1,2,...,N
2,3,...,N,1
3,4,...,N,1,2
···
N, 1, ... , ,N − 1
For instance, for the example above, we would consider each of the following as possibilities for the second row.
1234
2341
3412
4123
Your task is to find the score for each of the above choices of the second row. In the example above, you would evaluate the following four tables,
7162~~7162~~7162~~7162
1234~~2341~~3412~~4123
and compute scores 9, 10, 10 and 11, respectively.
Approach
For each of the N possible ways to rotate the second row, we calculate the sum of each column in the table by adding the elements from the first row and the rotated second row. The goal is to find the maximum sum from each column, and keep track of the highest of these maximums for each rotation. To efficiently handle this, we use two arrays that store the prefix maximums and suffix maximums of the sums, which helps in calculating the highest sum for each rotation without recalculating it from scratch. Finally, we output the highest sum for the initial configuration followed by the scores for each of the rotations.
Time Complexity
The time complexity is O(N) as we loop through the array and perform constant-time operations for each rotation.
Space Complexity
The space complexity is O(N) because we use additional arrays to store prefix and suffix maximums.