| 模型 | 模型答案 | 测试结果 |
|---|---|---|
| 金声玉亮2.0 | ```python def max_sum_rectangular_grid(grid, n): # Initialize the maximum sums for the current and previous columns max_sum_incl_prev = max(grid[0][0], grid[1][0]) max_sum_excl_prev = 0 for i in range(1, n): # Calculate the maximum sum including the current column max_sum_incl_curr = max(max_sum_excl_prev + grid[0][i], max_sum_excl_prev + grid[1][i]) # Calculate the maximum sum excluding the current column max_sum_excl_curr = max(max_sum_incl_prev, max_sum_excl_prev) # Update the previous sums for the next iteration max_sum_incl_prev = max_sum_incl_curr max_sum_excl_prev = max_sum_excl_curr # The result is the maximum of the last calculated sums return max(max_sum_incl_prev, max_sum_excl_prev) # Test cases assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 ``` [DONE] |
pass 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| deepseekr1 | To solve this problem, we need to find the maximum sum of elements from a 2xN grid such that no two chosen elements are adjacent. Adjacent elements are defined as those sharing a common edge, either horizontally or vertically. ### Approach The problem can be efficiently solved using dynamic programming. The key insight is to track two states for each column: the maximum sum when we take an element from the current column and the maximum sum when we do not take any element from the current column. By iterating through each column and updating these states, we can determine the maximum possible sum while respecting the adjacency constraint. 1. **Dynamic Programming States**: - `a`: The maximum sum when we do not take any element from the current column. - `b`: The maximum sum when we take the maximum element from the current column. 2. **Transitions**: - For each column, compute the maximum value of the two elements in that column. - Update the states: - `new_a` (not taking the current column) is the maximum of the previous `a` and `b`. - `new_b` (taking the current column) is the sum of the previous `a` (since we cannot take the previous column) and the maximum value of the current column. 3. **Initialization**: - Start with the first column where `a` is initialized to 0 (not taking the first column) and `b` is initialized to the maximum value of the first column. ### Solution Code ```python def max_sum_rectangular_grid(grid, n): if n == 0: return 0 max_vals = [max(grid[0][i], grid[1][i]) for i in range(n)] a = 0 # Represents not taking the first column b = max_vals[0] # Represents taking the first column for i in range(1, n): new_a = max(a, b) new_b = a + max_vals[i] a, b = new_a, new_b return max(a, b) ``` ### Explanation 1. **Initialization**: - Compute the maximum value for each column to simplify the decision of which element to take if we choose that column. - Initialize `a` to 0 (no elements taken from the first column) and `b` to the maximum value of the first column. 2. **Iteration**: - For each subsequent column, update `a` and `b` based on the previous values. - `new_a` is the maximum of the previous `a` and `b`, indicating the best sum without taking the current column. - `new_b` adds the maximum value of the current column to the previous `a`, ensuring no adjacent columns are taken. 3. **Result**: - The final result is the maximum of `a` and `b`, representing the highest possible sum where no two chosen elements are adjacent. This approach efficiently computes the solution in O(N) time complexity, where N is the number of columns, using constant space for the dynamic programming states. |
pass 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| gpto1 | ```python def max_sum_rectangular_grid(grid, n): # Get the maximum number from each column nums = [max(grid[0][i], grid[1][i]) for i in range(n)] if n == 0: return 0 elif n == 1: return nums[0] # Initialize dp array to store maximum sums dp = [0] * n dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) # Compute the maximum sum without adjacent numbers for i in range(2, n): dp[i] = max(nums[i] + dp[i-2], dp[i-1]) return dp[-1] ``` |
pass 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| GPT-4o | To solve this problem, we need to implement a dynamic programming solution where we keep track of the maximum sums by choosing or not choosing elements from the given 2xN grid. Here’s the step-by-step solution: 1. Create a 1D array `dp` where `dp[i]` will store the maximum sum we can get without considering adjacent elements up to the i-th column. 2. Initialize the first two elements of the `dp` array. 3. Iterate through the columns of the grid and update the `dp` array based on the maximum values chosen from either of the two rows at each column while ensuring non-adjacency. 4. Return the last element of the `dp` array, which will contain the maximum sum. Here's the implementation of the `max_sum_rectangular_grid` function: ```python def max_sum_rectangular_grid(grid, n): if n == 0: return 0 if n == 1: return max(grid[0][0], grid[1][0]) # Create dp array dp = [0] * n # Initialize the first two elements dp[0] = max(grid[0][0], grid[1][0]) dp[1] = max(grid[0][1], grid[1][1], dp[0]) # Fill the dp array for i in range(2, n): dp[i] = max(dp[i-1], dp[i-2] + max(grid[0][i], grid[1][i])) return dp[-1] # Tests assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 ``` This function ensures that no two chosen numbers are adjacent and computes the maximum sum efficiently using dynamic programming. |
pass 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| llama3.1-70B-Instruct | def max_sum_rectangular_grid(grid, n): incl = 0 excl = 0 for i in range(n): # Current max excluding i new_excl = max(incl, excl) # Current max including i incl = excl + max(grid[0][i], grid[1][i]) excl = new_excl # Return max of incl and excl return max(incl, excl) |
pass 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| llama3.1-405B-Instruct | def max_sum_rectangular_grid(grid, n): if n == 0: return 0 elif n == 1: return max(grid[0][0], grid[1][0]) else: dp = [[0 for _ in range(n)] for _ in range(2)] dp[0][0] = grid[0][0] dp[1][0] = grid[1][0] dp[0][1] = max(grid[0][0], grid[0][1]) dp[1][1] = max(grid[1][0], grid[1][1]) for i in range(2, n): dp[0][i] = max(dp[0][i-1], dp[1][i-2] + grid[0][i]) dp[1][i] = max(dp[1][i-1], dp[0][i |
failed 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| DeepSeek-Coder-V2 | ```python def max_sum_rectangular_grid(grid, n): # Initialize the maximum sums for the current and previous columns max_sum_incl_prev = max(grid[0][0], grid[1][0]) max_sum_excl_prev = 0 for i in range(1, n): # Calculate the maximum sum including the current column max_sum_incl_curr = max(max_sum_excl_prev + grid[0][i], max_sum_excl_prev + grid[1][i]) # Calculate the maximum sum excluding the current column max_sum_excl_curr = max(max_sum_incl_prev, max_sum_excl_prev) # Update the previous sums for the next iteration max_sum_incl_prev = max_sum_incl_curr max_sum_excl_prev = max_sum_excl_curr # The result is the maximum of the last calculated sums return max(max_sum_incl_prev, max_sum_excl_prev) # Test cases assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 ``` [DONE] |
pass 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| Qwen2-72B-Instruct | 'def max_sum_rectangular_grid(grid, n): dp = [[0 for _ in range(n+1)] for _ in range(2)] dp[0][1] = grid[0][0] dp[1][1] = grid[1][0] for i in range(2, n+1): dp[0][i] = max(dp[1][i-1], dp[0][i-1]) + grid[0][i-1] dp[1][i] = max(dp[0][i-1], dp[1][i-1]) + grid[1][i-1] return max(dp[0][n], dp[1][n])' [DONE] |
wrong_answer 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| baichuan4 | To solve the task of finding the maximum sum in a 2 x n rectangular grid such that no two chosen numbers are adjacent, we can use dynamic programming. We'll create a list to store the maximum sum at each step, avoiding taking adjacent numbers. Here's the function to accomplish this: ```python def max_sum_rectangular_grid(grid, n): # Initialize the list with the first and second elements of the grid dp = [grid[0][0], grid[1][0]] # Iterate through the rest of the elements in the grid for i in range(2, n): # The maximum sum at this step is the maximum of: # 1. The current element in the first row plus the maximum sum without the previous element in the first row # 2. The current element in the second row plus the maximum sum without the previous element in the second row dp.append(max(grid[0][i] + dp[i - 2], grid[1][i] + dp[i - 1])) # The maximum sum of the entire grid is the maximum of the last two elements in dp return max(dp[-1], dp[-2]) # Tests assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0] ], 3) == 7 assert max_sum_rectangular_grid([ [1, 2, 3, 4, 5], [6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 ``` This function works by iterating through each column of the grid, starting from the third column, and calculating the maximum sum that can be obtained by either including or excluding the current element based on the previously calculated sums. It then returns the maximum of the last two calculated sums, which represents the maximum sum possible without choosing adjacent numbers. |
wrong_answer 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| doubao | ' def max_sum_rectangular_grid(grid, n): if n == 1: return max(grid[0][0], grid[1][0]) dp = [[0] * n for _ in range(2)] dp[0][0] = grid[0][0] dp[1][0] = grid[1][0] for i in range(1, n): dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] + grid[0][i]) dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + grid[1][i]) return max(dp[0][n - 1], dp[1][n - 1])' [DONE] |
wrong_answer 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| minimax | To solve the problem of finding the maximum sum such that no two chosen numbers are adjacent for a given rectangular grid of dimension 2 x n, we can use dynamic programming. We will iterate through the columns and at each step, we will decide whether to take the maximum of the two rows or to skip one of them to avoid adjacency. Here's the function that implements this logic: ```python def max_sum_rectangular_grid(grid, n): if n == 0: return 0 elif n == 1: return max(grid[0][0], grid[1][0]) # Initialize the previous and current maximum sums prev_max = max(grid[0][0], grid[1][0]) curr_max = max(prev_max, grid[0][1], grid[1][1]) # Iterate through the columns starting from the second one for i in range(2, n): # Calculate the new maximum sum by considering the current column new_max = max(curr_max, prev_max + grid[0][i], prev_max + grid[1][i]) # Update the previous and current maximum sums for the next iteration prev_max, curr_max = curr_max, new_max return curr_max # Test cases assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 ``` This function should pass the provided test cases. |
pass 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| kimi | Certainly! Let's tackle each task one by one. 1. **Function to find similar elements from two tuple lists:** ```python def similar_elements(test_tup1, test_tup2): res = tuple(sorted(set(test_tup1) & set(test_tup2))) return res ``` 2. **Function to identify non-prime numbers:** ```python import math def is_not_prime(n): if n <= 1: return True for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return True return False ``` 3. **Function to find the largest integers from a given list using heap queue algorithm:** ```python import heapq def heap_queue_largest(nums, n): largest_nums = heapq.nlargest(n, nums) return largest_nums ``` 4. **Function to find out the maximum sum such that no two chosen numbers are adjacent for the given rectangular grid of dimension 2 x n:** ```python def max_sum_rectangular_grid(grid, n): if n == 0: return 0 elif n == 1: return max(grid[0][0], grid[1][0]) # Initialize the dp array dp = [0] * n dp[0] = max(grid[0][0], grid[1][0]) dp[1] = max(dp[0], grid[0][1], grid[1][1]) for i in range(2, n): dp[i] = max(dp[i-1], dp[i-2] + max(grid[0][i], grid[1][i])) return dp[-1] ``` Each function should pass the tests you've provided. Let's go through them one by one: 1. `similar_elements` should return a tuple of the common elements between two tuples. 2. `is_not_prime` should return `True` if a number is not prime and `False` otherwise. 3. `heap_queue_largest` should return the `n` largest numbers from a list using the heap queue algorithm. 4. `max_sum_rectangular_grid` should return the maximum sum of elements in a 2xN grid where no two chosen elements are adjacent. |
failed 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| wenxinyiyan | Here are the solutions to the given tasks: 1. Finding similar elements from two tuple lists: ```python def similar_elements(test_tup1, test_tup2): res = tuple(set(test_tup1) & set(test_tup2)) return res ``` The function `similar_elements` takes two tuple lists as input and returns a tuple containing the similar elements from both lists. It uses the set intersection operation (`&`) to find the common elements and then converts the result back to a tuple. 2. Identifying non-prime numbers: ```python import math def is_not_prime(n): if n < 2: return True for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return True return False ``` The function `is_not_prime` takes an integer `n` as input and returns `True` if it is not a prime number, and `False` otherwise. It checks if `n` is less than 2 (not prime) and then iterates from 2 to the square root of `n` to check for any divisors. If a divisor is found, it returns `True` indicating that the number is not prime. Note: There was a logical error in the provided code snippet. The function should return `False` for prime numbers and `True` for non-prime numbers. The corrected code reflects this. 3. Finding the largest integers from a given list using the heap queue algorithm: ```python import heapq as hq def heap_queue_largest(nums, n): largest_nums = hq.nlargest(n, nums) return largest_nums ``` The function `heap_queue_largest` takes a list of numbers `nums` and an integer `n` as input. It uses the `heapq.nlargest()` function to find the `n` largest numbers from the list and returns them as a list. 4. Finding the maximum sum such that no two chosen numbers are adjacent in a rectangular grid: ```python def max_sum_rectangular_grid(grid, n): if not grid or not grid[0]: return 0 rows = len(grid) cols = len(grid[0]) # Create a flattened list of numbers from the grid numbers = [grid[i][j] for i in range(rows) for j in range(cols)] # Create a list to store the maximum sums for each column max_sums = [0] * cols # Calculate the maximum sums for each column using dynamic programming for j in range(cols): # Initialize the maximum sum for the current column max_sum = 0 # Iterate over the rows and update the maximum sum for the current column for i in range(rows): # Calculate the current sum by adding the number from the grid # and subtracting the maximum sum from the previous column (if available) current_sum = numbers[i * cols + j] if j > 0: current_sum -= max_sums[j - 1] # Update the maximum sum for the current column max_sum = max(max_sum, current_sum) # Store the maximum sum for the current column max_sums[j] = max_sum + max_sums[j - 1] if j > 0 else max_sum # Return the maximum sum for the last column return max_sums[-1] ``` The function `max_sum_rectangular_grid` takes a rectangular grid (represented as a list of lists) and an integer `n` (the number of columns) as input. It uses dynamic programming to calculate the maximum sum such that no two chosen numbers are adjacent. The function flattens the grid into a list of numbers, creates a list to store the maximum sums for each column, and then iterates over the columns to calculate the maximum sums. Finally, it returns the maximum sum for the last column. Note: The provided code snippet for this task was incorrect, so I provided a new implementation based on the problem description. Please let me know if you need any further assistance! |
failed 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| zhipu | To solve this problem, we need to consider the constraints that no two chosen numbers can be adjacent. This includes both horizontally and vertically adjacent cells. We can use dynamic programming to efficiently compute the maximum sum. Here's a step-by-step approach: 1. Initialize a DP array to store the maximum sum up to each column. 2. For each column, compute the maximum sum considering the current column and the best possible sum from previous non-adjacent columns. Let's implement the function: ```python def max_sum_rectangular_grid(grid, n): if n == 0: return 0 # Initialize the DP array dp = [0] * n # Base case: the first column dp[0] = max(grid[0][0], grid[1][0]) if n == 1: return dp[0] # Second column dp[1] = max(dp[0], grid[0][1], grid[1][1]) for i in range(2, n): # Choose the current column and add the best sum from non-adjacent columns dp[i] = max(grid[0][i] + max(dp[i-2], dp[i-3] if i > 2 else 0), grid[1][i] + max(dp[i-2], dp[i-3] if i > 2 else 0), dp[i-1]) # Not choosing the current column return dp[-1] # Test cases assert max_sum_rectangular_grid([[1, 4, 5], [2, 0, 0]], 3) == 7 assert max_sum_rectangular_grid([[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]], 5) == 24 assert max_sum_rectangular_grid([[7, 9, 11, 15, 19], [21, 25, 28, 31, 32]], 5) == 81 print("All tests passed!") ``` ### Explanation: 1. **Initialization**: We initialize a DP array `dp` where `dp[i]` represents the maximum sum we can achieve up to the `i-th` column. 2. **Base Cases**: - For the first column, we take the maximum of the two possible values. - For the second column, we consider the maximum of taking either value in the second column or the value from the first column. 3. **Dynamic Programming Transition**: - For each subsequent column, we consider two main choices: - Taking the value from the top or bottom of the current column and adding it to the best sum from non-adjacent previous columns (`dp[i-2]` or `dp[i-3]` if available). - Not taking the current column's value and thus the best sum remains `dp[i-1]`. This approach ensures that no two chosen numbers are adjacent, and we compute the maximum possible sum efficiently using dynamic programming. The provided test cases confirm the correctness of the implementation. |
pass 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| gpto1 | ```python def max_sum_rectangular_grid(grid, n): # Get the maximum number from each column nums = [max(grid[0][i], grid[1][i]) for i in range(n)] if n == 0: return 0 elif n == 1: return nums[0] # Initialize dp array to store maximum sums dp = [0] * n dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) # Compute the maximum sum without adjacent numbers for i in range(2, n): dp[i] = max(nums[i] + dp[i-2], dp[i-1]) return dp[-1] ``` |
pass 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |
| deepseekv3 | To solve the problem of finding the maximum sum in a 2 x n grid such that no two chosen numbers are adjacent, we can use dynamic programming. The idea is to consider two scenarios for each column: either we take the top element of the column or the bottom element, ensuring that we don't take adjacent elements from the previous column. Here's the Python function to achieve this: ```python def max_sum_rectangular_grid(grid, n): # Initialize two variables to store the maximum sums # when the last column's top or bottom element is chosen top = grid[0][0] bottom = grid[1][0] # Iterate through each column starting from the second one for i in range(1, n): # Calculate the new top and bottom values new_top = grid[0][i] + max(bottom, 0) new_bottom = grid[1][i] + max(top, 0) # Update the top and bottom values for the next iteration top, bottom = new_top, new_bottom # Return the maximum of the top and bottom sums return max(top, bottom) # Test cases assert max_sum_rectangular_grid([[1, 4, 5], [2, 0, 0]], 3) == 7 assert max_sum_rectangular_grid([[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]], 5) == 24 assert max_sum_rectangular_grid([[7, 9, 11, 15, 19], [21, 25, 28, 31, 32]], 5) == 81 ``` ### Explanation: 1. **Initialization**: We start by initializing `top` and `bottom` variables with the values of the first column's top and bottom elements. 2. **Iteration**: For each column starting from the second one, we calculate the new possible values for `top` and `bottom`: - `new_top` is the current top element plus the maximum of the previous `bottom` and 0 (to ensure we don't take adjacent elements). - `new_bottom` is the current bottom element plus the maximum of the previous `top` and 0. 3. **Update**: We update `top` and `bottom` with the newly calculated values. 4. **Result**: After processing all columns, the maximum sum is the maximum of the final `top` and `bottom` values. This approach ensures that we never take two adjacent elements from the grid, and we efficiently compute the maximum sum using dynamic programming. |
wrong_answer 测试用例：assert max_sum_rectangular_grid([ [1, 4, 5], [2, 0, 0 ] ], 3) == 7 assert max_sum_rectangular_grid([ [ 1, 2, 3, 4, 5], [ 6, 7, 8, 9, 10] ], 5) == 24 assert max_sum_rectangular_grid([ [7, 9, 11, 15, 19], [21, 25, 28, 31, 32] ], 5) == 81 |