题解 | #环形数组的连续子数组最大和#java小白

环形数组的连续子数组最大和

https://www.nowcoder.com/practice/53a9f1ba687440cc9c641c2b042a59d7

本题用动态规划求解

本题难点在于这个数组是一个环,第一个元素的前一个元素时最后一个元素,不然就是简单的求最大和的连续子序列
状态转移方程为:
dp[i] = max(dp[i]+ints[i],ints[i])
dp为以第i个元素结尾的子序列的最大和

而求最大和,最大和有两种情况,包含首尾以及不包含
分清楚情况,然后计算就是算出两种情况的大小,相比返回最大值即可
当已知一种情况的最大值时,另一种的最大值即为总和减去最小值,因为最大最小两个子序列是连续的,试想一下,如果一段连续的序列大于零,那就自动归于最大值序列了,那小于零呢?
所以总的减去最小的即为相反情况

特殊情况:当数组全零或者全为负数时,直接返回最大值即可
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(
                new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        int ans = Integer.MIN_VALUE;
        int length = 0;
        st.nextToken();
        length = (int) st.nval;
        if (length == 1){
            st.nextToken();
            ans = (int) st.nval;
            pw.println(ans);
            pw.flush();
            return;
        }
        int[] ints = new int[length];
        for (int i = 0; i < length; i++) {
            st.nextToken();
            ints[i] = (int) st.nval;
        }

        int sum = ints[0];//和
        int dpMax = ints[0];//dp
        int tempMax = ints[0];//最大值
        int dpMin = ints[0];
        int tempMin = ints[0];
        for (int i = 1; i < length; i++) {
          sum += ints[i];
          dpMax = Math.max(dpMax+ints[i],ints[i]);
          tempMax = Math.max(tempMax,dpMax);
          dpMin = Math.min(dpMin+ints[i],ints[i]);
          tempMin = Math.min(tempMin,dpMin);
        }

        if (tempMax <= 0){
            ans = tempMax;

        }else {
            ans = Math.max(tempMax,sum-tempMin);
        }
        

        pw.println(ans);
        pw.flush();
    }
}
#动态规划#
动态规划题解 文章被收录于专栏

个人动态规划题解合集

全部评论

相关推荐

兄弟们,实习都是在接各种api,该怎么包装简历
仁者伍敌:感觉我自己做小项目也是各种api啊,我要怎么包装简历
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
牛客83700679...:简历抄别人的,然后再投,有反馈就是简历不行,没反馈就是学历不行,多投多改只要技术不差机会总会有的
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 10:39
一个证都没&nbsp;我能填什么
程序员小白条:别人有,你为什么没有,还是这个道理,社会就是比较,竞争,淘汰,你要安逸,那么就要做好淘汰的准备
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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