- 53 Maximum Subarray 找和最大子数组（找最小的话 元素取反求最大就行）
- 从前向后 计算sum同时 维持最小的前缀和
- dp dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0); dp[i]是已i元素结尾的子数组最大和
- lt138 Subarray Sum
- 题目：找一个和为零的子数组
- 思路：转化为找两个前缀和相同的子数组 中间的数和为零；
- 注意：要put(0, -1)；找到的和相同index返回时要加一 因为是要求中间的数 不包括上一个
- lt139 Subarray Sum Closest 找一个和最接近零的子数组 转化为找两个前缀和最接近的子数组;注意要添加Pair[0, 0] 计算下表0-2子数组和 用到presum[2]-presum[-1]
- Prefix Sum + Sort (Offline Algorithm)
Find the subarray sum closet to 0 => find two prefix sum closet to each other => find min difference in sorted prefix sum array
Sort (prefixSum, index) pair
Time Complexity: O(nlogn)
- 另一种解法
Prefix Sum + TreeMap (Online Algorithm)
Key: prefix sum Value: index
TreeMap is implemented using Red Black Tree (Balanced BST), can be used to find the closet element Ceiling/Floor
Time Complexity: O(nlogn)
- 121 Best Time to Buy and Sell Stock 有一点前缀和的意思 不过注意这里是要求利益的前缀和 所以用前缀和反而没有直接记录之前最小并维持一个全局最大利益来的简单
- lt405 Submatrix Sum
- 题目：求一个二维数组中某个子矩阵和为零
- 思路：枚举上行下行并在之前做前缀和 O(n^3)
- 注意：和之前那个题一样 要put(0, -1)；找到的和相同index返回时要加一 因为是要求中间的数 不包括上一个
- lt944 Maximum Submatrix
- 题目：求一个二维数组中最大子矩阵和
- 思路：枚举上行下行并在之前做前缀和 O(n^3)
- 304 Range Sum Query 2D - Immutable
- 308 Range Sum Query 2D - Mutable
53. Maximum Subarray 找和最大的子数组
class Solution {
public int maxSubArrayPrefixSum(int[] nums) {
if(nums==null || nums.length==0)
return 0;
int min = 0;
int sum = 0;
int result = Integer.MIN_VALUE;
for(int i=0; i<nums.length; i++){
sum = sum+nums[i];
result = Math.max(result, sum-min);
min = Math.min(min, sum);
}
return result;
}
}
public int maxSubArrayDP(int[] A) {
int n = A.length;
int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
dp[0] = A[0];
int max = dp[0];
for(int i = 1; i < n; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
lt138 Subarray Sum
public class Solution {
/**
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number and the index of the last number
*/
public List<Integer> subarraySum(int[] nums) {
// write your code here
List<Integer> list = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0;
for(int i=0; i<nums.length; i++){
sum = sum+nums[i];
if(map.containsKey(sum)){
int index = map.get(sum);
//注意这里加一
list.add(index+1);
list.add(i);
return list;
}else{
map.put(sum, i);
}
}
return list;
}
}
139. Subarray Sum Closest
public class Solution {
/*
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number and the index of the last number
*/
class pair{
int index;
int sum;
pair(int index, int sum){
this.index = index;
this.sum = sum;
}
}
public int[] subarraySumClosest(int[] nums) {
// write your code here
int[] result = new int[2];
if(nums==null)
return result;
if(nums.length==0)
return new int[]{0,0};
pair[] sums = new pair[nums.length+1];
sums[0] = new pair(0, 0);
int prev = 0;
for(int i=1; i<=nums.length; i++){
// sums[i] = new pair(i, sums[i-1].sum+nums[i-1]);
sums[i] = new pair(i, prev + nums[i-1]);
prev = sums[i].sum;
}
Arrays.sort(sums, new Comparator<pair>() {
public int compare(pair a, pair b) {
return a.sum - b.sum;
}
});
int ans = Integer.MAX_VALUE;
for(int i=1; i<sums.length; i++){
if(ans>sums[i].sum-sums[i-1].sum){
ans = sums[i].sum-sums[i-1].sum;
result[0] = sums[i-1].index-1;
result[1] = sums[i].index-1;
Arrays.sort(result);
result[0]++;
}
}
return result;
}
}
121 Best Time to Buy and Sell Stock
class Solution {
public int maxProfit(int[] nums) {
if(nums==null || nums.length<=1){
return 0;
}
int max = 0;
int min = Integer.MAX_VALUE;
for(int i=0; i<nums.length; i++){
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]-min);
}
return max;
}
}
lt405 Submatrix Sum
public class Solution {
/*
* @param matrix: an integer matrix
* @return: the coordinate of the left-up and right-down number
*/
public int[][] submatrixSum(int[][] matrix) {
// write your code here
int[][] result = new int[2][2];
int[][] sums = new int[matrix.length][matrix[0].length];
for(int col=0; col<matrix[0].length; col++){
int sum = 0;
for(int row=0; row<matrix.length; row++){
sum = sum+matrix[row][col];
sums[row][col] = sum;
}
}
for(int top=0; top<matrix.length; top++){
for(int bot=top; bot<matrix.length; bot++){
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0;
for(int i=0; i<matrix[0].length; i++){
sum = top>0 ? sum + sums[bot][i] - sums[top-1][i] : sum + sums[bot][i];
if(map.containsKey(sum)){
result[0][0] = top;
result[0][1] = map.get(sum)+1;
result[1][0] = bot;
result[1][1] = i;
return result;
}else{
map.put(sum, i);
}
}
}
}
return result;
}
}
lt944 Maximum Submatrix
public class Solution {
/**
* @param matrix: the given matrix
* @return: the largest possible sum
*/
public int maxSubmatrix(int[][] matrix) {
// write your code here
if(matrix==null || matrix.length==0 || matrix[0].length==0)
return 0;
int[][] sums = new int[matrix.length][matrix[0].length];
for(int col=0; col<matrix[0].length; col++){
int sum = 0;
for(int row=0; row<matrix.length; row++){
sum = sum + matrix[row][col];
sums[row][col] = sum;
}
}
int result = Integer.MIN_VALUE;
for(int top=0; top<matrix.length; top++){
for(int bot=top; bot<matrix.length; bot++){
int sum = 0;
int min = 0;
for(int i=0; i<matrix[0].length; i++){
sum = top>0 ? sum+sums[bot][i]-sums[top-1][i] : sum+sums[bot][i];
result = Math.max(result, sum-min);
min = Math.min(min, sum);
}
}
}
return result;
}
}
304 Range Sum Query 2D - Immutable
class NumMatrix {
int[][] sums;
public NumMatrix(int[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0]==null || matrix[0].length==0)
return;
sums = new int[matrix.length+1][matrix[0].length+1];
for(int i=1; i<=matrix.length; i++){
int sum = 0;
for(int j=1; j<=matrix[0].length; j++){
sum = sum+matrix[i-1][j-1];
sums[i][j] = sum + sums[i-1][j];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
if(sums==null)
return -1;
return sums[row2+1][col2+1]-sums[row2+1][col1] - sums[row1][col2+1] + sums[row1][col1];
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/
308 Range Sum Query 2D - Mutable
class NumMatrix {
int[][] sums;
int[][] matrix;
public NumMatrix(int[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0]==null || matrix[0].length==0)
return;
sums = new int[matrix.length+1][matrix[0].length+1];
this.matrix = matrix;
for(int i=1; i<=matrix.length; i++){
int sum = 0;
for(int j=1; j<=matrix[0].length; j++){
sum = sum + matrix[i-1][j-1];
sums[i][j] = sums[i-1][j] + sum;
}
}
}
public void update(int row, int col, int val) {
if(sums==null)
return;
int delta = val - matrix[row][col];
System.out.println(delta);
matrix[row][col] = val;
for(int i=row+1; i<sums.length; i++){
for(int j=col+1; j<sums[0].length; j++){
sums[i][j] = sums[i][j] + delta;
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
if(sums==null)
return -1;
return sums[row2+1][col2+1]+sums[row1][col1]-sums[row2+1][col1]-sums[row1][col2+1];
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* obj.update(row,col,val);
* int param_2 = obj.sumRegion(row1,col1,row2,col2);
*/
网友评论