剑指offer-题31：连续子数组的最大和

刺骨的言语ヽ痛彻心扉 2022-05-28 09:21 117阅读 0赞

## **题目描述** ##

输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如：输入数组为\{ 1, -2, 3, 10, -4, 7, 2, -5 \}，和最大的子数组为\{3, 10, -4, 7, 2\},因此输出为该子数组的和18。

实验平台：[牛客网][Link 1]

--------------------

## **解决思路：** ##

![这里写图片描述][70]  
![这里写图片描述][70 1]

java:

public class Solution {
        public int FindGreatestSumOfSubArray(int[] array) {
            if (array == null || array.length == 0) {
                return 0;
            } else {
                int curSum = 0;
                int maxSum = 0x80000000; // int类型的最小值
                for (int i = 0; i < array.length; i++) {
                    if (curSum <= 0) {
                        curSum = array[i];
                    } else {
                        curSum += array[i];
                    }
                    if (curSum > maxSum) {
                        maxSum = curSum;
                    }
                }
                return maxSum;
            }
        }
    }

python:

略

[Link 1]: https://www.nowcoder.com/ta/coding-interviews?page=1
[70]: /images/20220528/095611196fa24cf48e798663feb915cc.png
[70 1]: /images/20220528/73ed067491e34a649f0176f32bd448f0.png

发表评论取消回复

表情：

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

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

相关阅读

相关剑指offer - 连续子数组的最大和

public class Solution { public int FindGreatestSumOfSubArray(int[] a) {

冷不防/ 2022年09月25日 01:28/ 0 赞/ 162 阅读

相关【剑指offer-Java版】31连续子数组的最大和

连续子数组最大和，要求O(n)时间复杂度思路：核心思想就是当前遍历数组的时候，遇到的是一个正数，计算这个正数加上已有的和得到一个新的和如果这个新的和比当前的正数大，那

左手的ㄟ右手/ 2022年08月21日 09:48/ 0 赞/ 110 阅读

相关剑指offer：连续子数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正

╰半橙微兮°/ 2022年08月05日 08:58/ 0 赞/ 171 阅读

相关剑指offer之面试题31连续子数组的最大和

问题描述：输入一个整形数组，数组里有正数也有负数。数组中一个或者连续的多个数组组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。实现代码如下：

深碍√TFBOYSˉ_/ 2022年07月24日 04:03/ 0 赞/ 146 阅读

相关剑指offer面试题[31]-连续数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候

我不是女神ヾ/ 2022年06月12日 14:39/ 0 赞/ 117 阅读

相关剑指offer-题31：连续子数组的最大和

题目描述输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如：输入数组为\{

刺骨的言语ヽ痛彻心扉/ 2022年05月28日 09:21/ 0 赞/ 118 阅读

相关剑指Offer-连续子数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候

秒速五厘米/ 2022年04月24日 00:50/ 0 赞/ 208 阅读

相关剑指offer:连续子数组的最大和

题目描述例如:\{6,-3,-2,7,-15,1,2,2\},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和。 AC C

港控/mmm°/ 2022年04月10日 08:59/ 0 赞/ 205 阅读

相关 31. 连续子数组的最大和《剑指Offer》(Java版)

题目描述 > 给一个数组，返回它的最大连续子序列的和，例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。

拼搏现实的明天。/ 2022年01月30日 11:27/ 0 赞/ 170 阅读

相关剑指offer：连续子数组的最大和

试题： HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问

柔光的暖阳◎/ 2021年06月24日 16:09/ 0 赞/ 383 阅读