最大不相邻子序列和

不相邻最大子序列和

http://www.nowcoder.com/questionTerminal/269b4dbd74e540aabd3aa9438208ed8d

图片说明
注意当 i>3 时,可以相隔 2 个位置获得最大值,因此,还需要比较 arr[i] 与 max[i-3] 的和。max 存储的是当前值作为子序列结尾可获取到的最大值

func subsequence( n int ,  array []int ) int64 {
    // write code here
    if n ==0{
        return 0
    }
    if n==1{
        return int64(array[0])
    }
    maxSum := make([]int64,n)
    var max int64 = math.MinInt64
    for i:=0;i<n;i++{
        if i==0 || i==1 {
            maxSum[i] = int64(array[i])
            if maxSum[i] > max{
                max =maxSum[i]
            }
            continue
        }
        maxSum[i] = findMax(int64(array[i]),int64(array[i])+maxSum[i-2])
        if i>3{
            maxSum[i] = findMax(maxSum[i],int64(array[i])+maxSum[i-3])
        }
        if maxSum[i] > max{
            max = maxSum[i]
        }
    }
    return max
}

func findMax(a,b int64)int64{
    if a>b{
        return a
    }
    return b
}
全部评论

相关推荐

不对是145个人…嗯…&nbsp;大家都没发现秋招提前批来了嘛..笑死我了
牛客39712426...:投了也是浪费时间,之前投米实习,除了浪费我时间写笔试题没有任何反馈,懒得投了
26届校招投递进展
点赞 评论 收藏
分享
07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务