连续子数组最大和--牛客NC19

约定不等于承诺〃 2024-04-01 14:12 73阅读 0赞

### 描述 ###

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

数据范围:

![e283395030c346eea7ce25044656eec9.png][]

要求:时间复杂度为 O(n)，空间复杂度为 O(n)

进阶:时间复杂度为 O(n)，空间复杂度为 O(1)

### 示例1 ###

输入：\[1,-2,3,10,-4,7,2,-5\]返回值：18  
说明：经分析可知，输入数组的子数组\[3,10,-4,7,2\]可以求得最大和为18

## 题解： ##

public class Solution {
        public int FindGreatestSumOfSubArray(int[] array) {
        //    //方法一：暴力法，双重循环，O(n^2)
        //    int sum = 0;
        //    int max = array[0];
        //    for(int i = 0 ;i<array.length;i++){
        //        //一次遍历后，sum清零从下一个元素开始再次遍历
        //        sum = 0;
        //        for(int j = i;j<array.length;j++){
        //            //sum一直是连续相加的，保证连续
        //            sum += array[j];
        //            //存储比较每加一次，得到最大值
        //            max = Math.max(sum,max);
    
        //        }
        //    }
        //方法二：优化动态规划
                int sum = 0;
                int max = array[0];
                for(int i = 0;i<array.length;i++){
                    sum = Math.max(sum + array[i],array[i]);
                    max = Math.max(max,sum);
    
                }
                return max;
    
     
        }
    }

[e283395030c346eea7ce25044656eec9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e940ecd7fd444a67a5debf83cac9f9ae.png

发表评论取消回复

表情：

评论列表（有 0 条评论，73人围观）

还没有评论，来说两句吧...

相关阅读

相关连续子数组最大和--牛客NC19

描述输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。数据范围: ![e2833950

约定不等于承诺〃/ 2024年04月01日 14:12/ 0 赞/ 74 阅读

相关牛客子矩阵最大累加和问题

题目链接：[https://www.nowcoder.com/practice/cb82a97dcd0d48a7b1f4ee917e2c0409?tpId=101&tqId=3

喜欢ヅ旅行/ 2023年06月04日 14:57/ 0 赞/ 15 阅读

相关牛客子数组最大异或和

题目链接：[https://www.nowcoder.com/practice/43f62c52fbac47feaeabe40ac1ab9091?tpId=101&tqId=3

系统管理员/ 2023年06月04日 14:56/ 0 赞/ 11 阅读

相关子数组最大乘积（C++牛客网）

解题思路：（1）注意负数，可能颠倒最大值和最小值 class Solution { public: double maxProduct(v

今天药忘吃喽~/ 2023年01月13日 04:07/ 0 赞/ 202 阅读

相关【LeetCode】连续子数组、子矩阵最大和问题

【LeetCode】连续子数组、子矩阵最大和问题文章目录【LeetCode】连续子数组、子矩阵最大和问题连续子数组的最大和★

曾经终败给现在/ 2022年11月13日 13:29/ 0 赞/ 200 阅读

相关 NC19 连续子数组的最大和（暴力法+动态规划）

暴力法 public class Solution { public int FindGreatestSumOfSubArray

ゞ浴缸里的玫瑰/ 2022年09月16日 15:20/ 0 赞/ 172 阅读

相关和最大的连续子数组

和最大的连续子数组，LeetCode标签：剑指 Offer 42. 连续子数组的最大和 int maxSubArray(vector<int>& nums) {

﹏ヽ暗。殇╰゛Y/ 2022年09月15日 15:51/ 0 赞/ 186 阅读

相关牛客题霸 NC19 子数组的最大累加和问题

https://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd 解决方案 Go fu

朱雀/ 2022年09月05日 04:08/ 0 赞/ 160 阅读

相关连续子数组最大和问题

1. 问题描述输入一个整形数组，求数组中连续的子数组使其和最大。比如，数组x ![132021534183635.png][] 应该返回 x\[2..6\]的和1

冷不防/ 2022年07月18日 01:12/ 0 赞/ 222 阅读

相关 10、连续子数组最大和

给定一个数组，求连续的几个子元素构成最大和的子集合： public class findMaxSum { public int FindGr

怼烎@/ 2022年05月27日 10:19/ 0 赞/ 237 阅读