Sponsored
Sponsored
This approach involves calculating the prefix sum for every column and iterating over pairs of row indices to form vertical strips. The idea is derived from simplifying the multidimensional problem to a manageable form by transforming it into a 1D problem with the help of prefix sums and leveraging subarray sum computation techniques.
Time Complexity: O(n^2 * m log m), where m = num of rows and n = num of columns. Space Complexity: O(m) for storing row sums.
1import bisect
2
3def maxSumSubmatrix(matrix, k):
4 if not matrix or not matrix[0]: return 0
5 max_sum = float('-inf')
6 rows, cols = len(matrix), len(matrix[0])
7
8 for left in range(cols):
9 row_sum = [0] * rows
10 for right in range(left, cols):
11 for r in range(rows):
12 row_sum[r] += matrix[r][right]
13 max_sum = max(max_sum, maxSumNoLargerThanK(row_sum, k))
14
15 return max_sum
16
17
18def maxSumNoLargerThanK(nums, k):
19 accu_sum, max_sum = 0, float('-inf')
20 accu_sums = [0]
21 for num in nums:
22 accu_sum += num
23 i = bisect.bisect_left(accu_sums, accu_sum - k)
24 if i < len(accu_sums):
25 max_sum = max(max_sum, accu_sum - accu_sums[i])
26 bisect.insort(accu_sums, accu_sum)
27 return max_sum
28The Python implementation uses a 2D prefix sum to convert the problem into finding a subarray sum no larger than k. We iterate over left and right column boundaries and compute row-wise sums in between. Then maxSumNoLargerThanK finds the maximum subarray sum no larger than k in these running row sums using a binary search approach (with the help of Python's bisect library) to maintain the cumulative sum.
This approach uses recursion to solve the problem by breaking it down into smaller subproblems and storing the results of these subproblems to avoid redundant calculations. Hence, it combines recursion with memoization.
Time Complexity: O(n)
Space Complexity: O(n) due to the memoization array
1
class Program {
static int[] memo;
static int Fib(int n) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = Fib(n-1) + Fib(n-2);
return memo[n];
}
static void Main() {
int n = 10; // Example
memo = new int[n + 1];
for (int i = 0; i <= n; i++) memo[i] = -1;
Console.WriteLine(Fib(n));
}
}This approach solves the problem iteratively, preventing the overhead of recursive function calls. It constructs a solution bottom-up and is generally more space-efficient.
Time Complexity: O(n)
Space Complexity: O(1)
1using System;
2
class Program {
static int Fib(int n) {
if (n <= 1) return n;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
static void Main() {
int n = 10; // Example
Console.WriteLine(Fib(n));
}
}The C# solution utilizes an array for memoization and solves the Fibonacci sequence recursively while storing results to improve efficiency.
The C# iterative solution helps utilize minimal space by merely updating variables that track the required Fibonacci numbers.