package main

import (
    "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
}