Given a 2D Array, :1 1 1 0 0 00 1 0 0 0 01 1 1 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0An hourglass in is a subset of values with indices falling in this pattern in 's graphical representation:a b c de f gThere are hourglasses in . An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in , then print the maximum hourglass sum. The array will always be .Example-9 -9 -9 1 1 1 0 -9 0 4 3 2-9 -9 -9 1 2 3 0 0 8 6 6 0 0 0 0 -2 0 0 0 0 1 2 4 0The hourglass sums are:-63, -34, -9, 12, -10, 0, 28, 23, -27, -11, -2, 10, 9, 17, 25, 18The highest hourglass sum is from the hourglass beginning at row , column :0 4 3 18 6 6Note: If you have already solved the Java domain's Java 2D Array challenge, you may wish to skip this challenge.Function DescriptionComplete the function hourglassSum in the editor below.hourglassSum has the following parameter(s):int arr[6][6]: an array of integersReturnsint: the maximum hourglass sumInput FormatEach of the lines of inputs contains space-separated integers .ConstraintsOutput FormatPrint the largest (maximum) hourglass sum found in .
Question
Given a 2D Array, :1 1 1 0 0 00 1 0 0 0 01 1 1 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0An hourglass in is a subset of values with indices falling in this pattern in 's graphical representation:a b c de f gThere are hourglasses in . An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in , then print the maximum hourglass sum. The array will always be .Example-9 -9 -9 1 1 1 0 -9 0 4 3 2-9 -9 -9 1 2 3 0 0 8 6 6 0 0 0 0 -2 0 0 0 0 1 2 4 0The hourglass sums are:-63, -34, -9, 12, -10, 0, 28, 23, -27, -11, -2, 10, 9, 17, 25, 18The highest hourglass sum is from the hourglass beginning at row , column :0 4 3 18 6 6Note: If you have already solved the Java domain's Java 2D Array challenge, you may wish to skip this challenge.Function DescriptionComplete the function hourglassSum in the editor below.hourglassSum has the following parameter(s):int arr[6][6]: an array of integersReturnsint: the maximum hourglass sumInput FormatEach of the lines of inputs contains space-separated integers .ConstraintsOutput FormatPrint the largest (maximum) hourglass sum found in .
Solution
The problem is asking to find the maximum sum of an hourglass in a 2D array. An hourglass in 2D array is a subset of values with indices falling in this pattern:
a b c d e f g
Here are the steps to solve this problem:
- Initialize a variable, maxSum, to a very small number.
- Iterate through each element in the 2D array. Since the hourglass is 3x3, we stop iteration at length-2 to avoid IndexOutOfBounds.
- For each element at index (i, j), calculate the sum of the hourglass with top-left corner at (i, j). The hourglass sum can be calculated as the sum of arr[i][j], arr[i][j+1], arr[i][j+2], arr[i+1][j+1], arr[i+2][j], arr[i+2][j+1], and arr[i+2][j+2].
- If the calculated sum is greater than maxSum, update maxSum.
- Continue this process for all valid (i, j) pairs in the 2D array.
- After iterating through all elements in the 2D array, maxSum will hold the maximum hourglass sum. Print or return this value.
This solution works in O(n^2) time, where n is the length of the input 2D array.
Similar Questions
Given an integer array arr, write a program to find the subarray which has the largest sum and return its sum. If the array is empty, return 0.Sample Input:9-2 -1 -3 4 -1 2 1 -5 4Sample Output: 6Explanation:The subarray is [4, -1, 2, 1] and the sum is 6
Write an efficient C program to find the sum of contiguous subarray within a one-dimensionalarray of integer which returns the largest sum.Explanation:Lets take the example of array {5,-3, 4}Possible contiguous subarray combinations are{5}, {-3}, {4}, {5,-3}, {-3,4}, {5,-3,4}The contiguous subarray {5,-3,4} has got the largest sum 6
n = len(grid) x = sum(max(grid[i][j] for i in range(n)) for j in range(n)) y = sum(max(grid[j][i] for i in range(n)) for j in range(n)) z = sum(grid[i][j] > 0 for i in range(n) for j in range(n)) return sum([x,y,z])
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer. Example 1:Input: arr = [1,15,7,9,2,5,10], k = 3Output: 84Explanation: arr becomes [15,15,15,9,10,10,10]
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.