2021-07-10:请返回arr中,求子数组的累加和,是<=K的并且是最大的。返回这个最大的累加和。
2021/7/10 23:38:30
本文主要是介绍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的并且是最大的。返回这个最大的累加和。的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-26Adobe国际认证(证书)认证价值详解
- 2024-07-2501.计算机组成原理和结构
- 2024-07-25城域网
- 2024-07-25为什么API经济在经济不确定时期表现突出
- 2024-07-24Python实现Java mybatis-plus 产生的SQL自动化测试SQL速度和判断SQL是否走索引
- 2024-07-24轻松获取天气信息:免费天气API一览
- 2024-07-24深入理解 Java17 新特性:Sealed Classes
- 2024-07-24大厂的第三方支付业务架构设计
- 2024-07-23docker及tomcat 部署java项目
- 2024-07-23Adobe国际认证详解-艺术设计专业的就业前景