前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2021-04-25:给定一个数组arr,和一个正数M,返回在arr的子数组在长度不超过M的情况下,求最大的累加和。

2021-04-25:给定一个数组arr,和一个正数M,返回在arr的子数组在长度不超过M的情况下,求最大的累加和。

作者头像
福大大架构师每日一题
发布2021-08-05 15:34:16
8640
发布2021-08-05 15:34:16
举报
文章被收录于专栏:福大大架构师每日一题

福大大 答案2021-04-25:

前缀和+左大右小的双端队列。时间太晚了,所以写得简单。

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

代码语言:javascript
复制
package main

import (
    "container/list"
    "fmt"
)

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

// O(N)的解法,最优解
func maxSum(arr []int, M int) int {
    if len(arr) == 0 || M < 1 {
        return 0
    }
    N := len(arr)
    //前缀和
    sum := make([]int, N)
    sum[0] = arr[0]
    for i := 1; i < N; i++ {
        sum[i] = sum[i-1] + arr[i]
    }

    //双端队列
    qmax := list.New()
    i := 0
    end := getMin(N, M)
    for ; i < end; i++ {
        for qmax.Len() > 0 && sum[qmax.Back().Value.(int)] <= sum[i] {
            qmax.Remove(qmax.Back())
        }
        qmax.PushBack(i)
    }

    max := sum[qmax.Front().Value.(int)]
    L := 0
    for ; i < N; L, i = L+1, i+1 {
        if qmax.Front().Value.(int) == L {
            qmax.Remove(qmax.Front())
        }
        for qmax.Len() > 0 && sum[qmax.Back().Value.(int)] <= sum[i] {
            qmax.Remove(qmax.Back())
        }
        qmax.PushBack(i)
        max = getMax(max, sum[qmax.Front().Value.(int)]-sum[L])
    }

    for ; L < N-1; L++ {
        if qmax.Front().Value.(int) == L {
            qmax.Remove(qmax.Front())
        }
        max = getMax(max, sum[qmax.Front().Value.(int)]-sum[L])
    }

    return max
}

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

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class46/Code04_MaxSumLengthNoMore.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-04-25,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档