Java教程

2021-07-10:请返回arr中,求子数组的累加和,是<=K的并且是最大的。返回这个最大的累加和。

本文主要是介绍2021-07-10:请返回arr中,求子数组的累加和,是<=K的并且是最大的。返回这个最大的累加和。,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

2021-07-10:请返回arr中,求子数组的累加和,是<=K的并且是最大的。返回这个最大的累加和。

福大大 答案2021-07-10:

时间紧。见代码。
时间复杂度:O(N*logN)。空间复杂度:O(N)。

代码用golang编写。代码如下:

package main

import (
    "fmt"
    "math"
    "sort"
)

func main() {
    arr := []int{1, 4, -3, 4, -5}
    ret := getMaxLessOrEqualK(arr, 7000)
    fmt.Println(ret)
}

// 请返回arr中,求个子数组的累加和,是<=K的,并且是最大的。
// 返回这个最大的累加和
func getMaxLessOrEqualK(arr []int, K int) int {
    // 记录i之前的,前缀和,按照有序表组织
    set := make([]int, 0)
    map0 := make(map[int]struct{})
    // 一个数也没有的时候,就已经有一个前缀和是0了
    set = append(set, 0)
    map0[0] = struct{}{}
    max := math.MinInt64
    sum := 0
    // 每一步的i,都求子数组必须以i结尾的情况下,求个子数组的累加和,是<=K的,并且是最大的
    for i := 0; i < len(arr); i++ {
        sum += arr[i] // sum -> arr[0..i];
        sort.Ints(set)
        index := NearestIndex(set, sum-K)
        if index != -1 {
            max = getMax(max, sum-index)
        }
        if _, ok := map0[sum]; !ok {
            set = append(set, sum) // 当前的前缀和加入到set中去
            map0[sum] = struct{}{}
        }
    }
    return max

}

func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

// 在arr上,找满足>=value的最左位置
func NearestIndex(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
            R = mid - 1
        } else {
            L = mid + 1
        }
    }
    return index
}

执行结果如下:
图片


左神java代码

这篇关于2021-07-10:请返回arr中,求子数组的累加和,是<=K的并且是最大的。返回这个最大的累加和。的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!