2021-04-04：给定一个非负数组arr，和一个正数m。 返回arr的所有子序列中累加和%m之后的最大值。
福大大 答案2021-04-04：
自然智慧即可。
1.递归，累加和。
2.动态规划，累加和。
3.动态规划，累加和%m。
4.双向动态规划，累加和%m。
代码用golang编写。代码如下：
package mainimport ( "fmt" "math/rand" "sort" "time")func main() { rand.Seed(time.Now().Unix()) const TOTAL = 500 RightCount := 0 for i := 0; i < TOTAL; i++ { arr := NewRandArr() m := rand.Intn(200) + 1 fmt.Println(arr, m) ret1 := max1(arr, m) fmt.Println("1.递归,累加和：", ret1) ret2 := max2(arr, m) fmt.Println("2.动态规划，累加和：", ret2) ret3 := max3(arr, m) fmt.Println("3.动态规划，累加和%m：", ret3) ret4 := max4(arr, m) fmt.Println("4.双向动态规划，累加和%m：", ret4) fmt.Println("---------------------") if ret1 == ret2 && ret1 == ret3 && ret1 == ret4 { RightCount++ } } fmt.Println("总数：", TOTAL) fmt.Println("正确：", RightCount)}//递归，算出所有子序列的累加和func max1(arr []int, m int) int { set := make(map[int]struct{}) process(arr, 0, 0, set) max := 0 for sum, _ := range set { max = getMax(max, sum%m) } return max}func process(arr []int, index int, sum int, set map[int]struct{}) { if index == len(arr) { set[sum] = struct{}{} } else { process(arr, index+1, sum, set) process(arr, index+1, sum+arr[index], set) }}func getMax(a int, b int) int { if a > b { return a } else { return b }}//2.动态规划，算出所有的累加和func max2(arr []int, m int) int { sum := 0 N := len(arr) for i := 0; i < N; i++ { sum += arr[i] } dp := make([][]bool, N) for i := 0; i < N; i++ { dp[i] = make([]bool, sum+1) } for i := 0; i < N; i++ { dp[i][0] = true } dp[0][arr[0]] = true for i := 1; i < N; i++ { for j := 1; j <= sum; j++ { dp[i][j] = dp[i-1][j] if j-arr[i] >= 0 { dp[i][j] = dp[i][j] || dp[i-1][j-arr[i]] } } } ans := 0 for j := 0; j <= sum; j++ { if dp[N-1][j] { ans = getMax(ans, j%m) } } return ans}//3.动态规划，算出所有的模m的累加和。数组长度巨大，m不大。func max3(arr []int, m int) int { N := len(arr) // 0...m-1 dp := make([][]bool, N) for i := 0; i < N; i++ { dp[i] = make([]bool, m) } for i := 0; i < N; i++ { dp[i][0] = true } dp[0][arr[0]%m] = true for i := 1; i < N; i++ { for j := 1; j < m; j++ { // dp[i][j] T or F dp[i][j] = dp[i-1][j] cur := arr[i] % m if cur <= j { dp[i][j] = dp[i][j] || dp[i-1][j-cur] } else { dp[i][j] = dp[i][j] || dp[i-1][m+j-cur] } } } ans := 0 for i := 0; i < m; i++ { if dp[N-1][i] { ans = i } } return ans}// 如果arr的累加和很大，m也很大// 但是arr的长度相对不大func max4(arr []int, m int) int { if len(arr) == 1 { return arr[0] % m } mid := (len(arr) - 1) / 2 sortSet1 :ɳ��,ɳ̲= make(map[int]struct{}) process4(arr, 0, 0, mid, m, sortSet1) sortSet2 := make(map[int]struct{}) process4(arr, mid+1, 0, len(arr)-1, m, sortSet2) ans := 0 s1 := make([]int, 0) for key, _ := range sortSet1 { s1 = append(s1, key) } sort.Ints(s1) //fmt.Println("s1:", s1) s2 := make([]int, 0) for key, _ := range sortSet2 { s2 = append(s2, key) } sort.Ints(s2) //fmt.Println("s2:", s2) for _, leftMod := range s1 { //ans = getMax(ans, leftMod + sortSet2.floor(m - 1 - leftMod)); index := NearestIndex2(s2, m-1-leftMod) if index >= 0 { ans = getMax(ans, leftMod+s2[index]) } else { ans = getMax(ans, leftMod) } } return ans}// 在arr上，找满足<=value的最右位置func NearestIndex2(arr []int, v int) int { L := 0 R := len(arr) - 1 index := -1 // 记录最右的对号 for L <= R { mid := L + (R-L)>>1 if arr[mid] <= v { index = mid L = mid + 1 } else { R = mid - 1 } } return index}// 从index出发，最后有边界是end+1，arr[index...end]func process4(arr []int, index int, sum int, end int, m int, sortSet map[int]struct{}) { if index == end+1 { sortSet[sum%m] = struct { }{} } else { process4(arr, index+1, sum, end, m, sortSet) process4(arr, index+1, sum+arr[index], end, m, sortSet) }}func NewRandArr() []int { arrLen := rand.Intn(10) + 5 arr := make([]int, arrLen) for i := 0; i < arrLen; i++ { arr[i] = rand.Intn(50) } return arr}执行结果如下：
左神java代码
评论