import java.util.TreeSet; public class Main { public int TaichiAndLand(int n, int m,…
- User
import java.util.TreeSet; public class Main { public int TaichiAndLand(int n, int m, int[][] arr, int K) { int maxSum = Integer.MIN_VALUE; for (int top = 0; top < n; top++) { int[] columnSum = new int[m]; for (int bottom = top; bottom < n; bottom++) { for (int col = 0; col < m; col++) { columnSum[col] += arr[bottom][col]; } maxSum = Math.max(maxSum, solve(columnSum, K)); } }
return maxSum; } private int solve(int[] nums, int K) { int sum = 0; int maxSum = Integer.MIN_VALUE; TreeSet cc = new TreeSet<>(); cc.add(0);
for (int num : nums) { sum += num; Integer prefix = cc.ceiling(sum - K); if (prefix != null) { maxSum = Math.max(maxSum, sum - prefix); }
cc.add(sum); }
return maxSum; }
Taichi and land convert it in cpp
- Assistant
Certainly! Below is the C++ equivalent of your provided Java code. This C++ version maintains the same logic and structure, using standard C++ libraries to achieve the desired functionality.
Java to C++ Conversion Overview
-
Class Structure: While Java uses classes extensively, C++ allows both class-based and function-based approaches. Here, we'll use a class structure similar to your Java code for clarity.
-
Data Structures:
- TreeSet in Java: In C++,
std::setis utilized, which provides similar functionality such as maintaining ordered elements and allowing efficient searches. - Vectors: C++
std::vectoris used in place of Java's 2D arrays for dynamic array handling.
- TreeSet in Java: In C++,
-
Functionality:
- The
TaichiAndLandfunction iterates over all possible submatrices, computes column sums, and uses thesolvefunction to find the maximum subarray sum that does not exceedK. - The
solvefunction uses a set to efficiently find the smallest prefix sum that allows the current subarray sum to be as large as possible without exceedingK.
- The
C++ Implementation
#include <bits/stdc++.h> using namespace std; class Main { public: // Function to find the maximum submatrix sum no larger than K int TaichiAndLand(int n, int m, vector<vector<int>> &arr, int K) { int maxSum = INT32_MIN; // Iterate over all possible top rows for(int top = 0; top < n; ++top){ // Initialize column sums to zero vector<int> columnSum(m, 0); // Iterate over all possible bottom rows for the current top for(int bottom = top; bottom < n; ++bottom){ // Update column sums with the current bottom row for(int col = 0; col < m; ++col){ columnSum[col] += arr[bottom][col]; } // Find the best subarray sum for the current column sums int currentMax = solve(columnSum, K); maxSum = max(maxSum, currentMax); } } return maxSum; } private: // Helper function to find the maximum subarray sum no larger than K int solve(vector<int> &nums, int K){ long long sum = 0; int maxSum = INT32_MIN; set<long long> prefixSums; prefixSums.insert(0); // Initialize with prefix sum 0 for(auto num : nums){ sum += num; // Find the smallest prefix sum >= (current sum - K) auto it = prefixSums.lower_bound(sum - (long long)K); if(it != prefixSums.end()){ maxSum = max(maxSum, (int)(sum - *it)); } // Insert the current prefix sum into the set prefixSums.insert(sum); } return maxSum; } }; // Example usage int main(){ Main solver; int n = 3, m = 3, K = 6; vector<vector<int>> arr = { {1, 0, 1}, {0, -2, 3}, {4, 5, 6} }; int result = solver.TaichiAndLand(n, m, arr, K); cout << "Maximum sum no larger than K is: " << result << endl; return 0; }Explanation of the C++ Code
-
TaichiAndLand Function:
- Parameters:
n: Number of rows in the matrix.m: Number of columns in the matrix.arr: 2D vector representing the matrix.K: The target sum constraint.
- Logic:
- Iterates over all possible pairs of top and bottom rows.
- For each pair, it computes the cumulative column sums.
- Calls the
solvefunction to find the maximum subarray sum for these column sums that does not exceedK. - Updates the
maxSumaccordingly.
- Parameters:
-
solve Function:
- Parameters:
nums: Vector of integers representing the current column sums.K: The target sum constraint.
- Logic:
- Uses a
std::setto keep track of prefix sums. - For each number in
nums, it updates the running sum. - Searches for the smallest prefix sum in the set that, when subtracted from the current sum, yields a value <=
K. - Updates
maxSumif a better sum is found. - Inserts the current sum into the set for future iterations.
- Uses a
- Parameters:
-
Main Function:
- Demonstrates how to use the
TaichiAndLandfunction with an example matrix and prints the result.
- Demonstrates how to use the
Notes
-
Performance: The time complexity of this solution is O(n² * m * log m), where
nis the number of rows andmis the number of columns. This is because there are O(n²) possible pairs of top and bottom rows, and for each pair, thesolvefunction operates in O(m log m) time due to the set operations. -
Edge Cases: Ensure that the input matrix and
Kare within the expected bounds to avoid integer overflow or other potential issues.
Feel free to modify the
mainfunction or integrate this class into your larger project as needed. -