363. Max Sum of Rectangle No Larger Than K #

package leetcode

import (
	"math"
)

// Solution 1 Binary Search
func maxSumSubmatrix(matrix [][]int, k int) int {
	// Convert to prefix sums
	for i := 0; i < len(matrix); i++ {
		for j := 1; j < len(matrix[0]); j++ {
			matrix[i][j] += matrix[i][j-1]
		}
	}
	sum, absMax, absMaxFound := make([]int, len(matrix)), 0, false
	for y1 := 0; y1 < len(matrix[0]); y1++ {
		for y2 := y1; y2 < len(matrix[0]); y2++ {
			for x := 0; x < len(matrix); x++ {
				if y1 == 0 {
					sum[x] = matrix[x][y2]
				} else {
					sum[x] = matrix[x][y2] - matrix[x][y1-1]
				}
			}
			curMax := kadaneK(sum, k)
			if !absMaxFound || curMax > absMax {
				absMax = curMax
				absMaxFound = true
			}
		}
	}
	return absMax
}

func kadaneK(a []int, k int) int {
	sum, sums, maxSoFar := 0, []int{}, math.MinInt32
	for _, v := range a {
		// The first loop inserts 0 first, because sum may be equal to k
		sums = insertSort(sums, sum)
		sum += v
		pos := binarySearchOfKadane(sums, sum-k)
		if pos < len(sums) && sum-sums[pos] > maxSoFar {
			maxSoFar = sum - sums[pos]
		}
	}
	return maxSoFar
}

func binarySearchOfKadane(a []int, v int) int {
	low, high := 0, len(a)
	for low < high {
		mid := low + (high-low)>>1
		if a[mid] < v {
			low = mid + 1
		} else {
			high = mid
		}
	}
	return low
}

func insertSort(a []int, v int) []int {
	// Similar to insertion sort, insert the element into the array in ascending order
	p := binarySearchOfKadane(a, v)
	a = append(a, 0)
	// Move all elements after p back, freeing position p to place v
	copy(a[p+1:], a[p:len(a)-1])
	a[p] = v
	return a
}

// Solution 2 Brute-force solution, times out
func maxSumSubmatrix1(matrix [][]int, k int) int {
	minNum := math.MaxInt64
	for row := range matrix {
		for col := 1; col < len(matrix[row]); col++ {
			if matrix[row][col] < minNum {
				minNum = matrix[row][col]
			}
		}
	}
	for row := range matrix {
		for col := 1; col < len(matrix[row]); col++ {
			matrix[row][col] += matrix[row][col-1]
		}
	}
	for i := k; ; i-- {
		if findSumSubmatrix(matrix, i) > 0 {
			return i
		}
	}
}

func findSumSubmatrix(matrix [][]int, target int) int {
	m, n, res := len(matrix), len(matrix[0]), 0
	for i := 0; i < n; i++ {
		for j := i; j < n; j++ {
			counterMap, sum := make(map[int]int, m), 0
			counterMap[0] = 1 // The problem guarantees there is a solution, so initialize this to 1
			for row := 0; row < m; row++ {
				if i > 0 {
					sum += matrix[row][j] - matrix[row][i-1]
				} else {
					sum += matrix[row][j]
				}
				res += counterMap[sum-target]
				counterMap[sum]++
			}
		}
	}
	return res
}