LeetCode53. 最大子序和

╰+攻爆jí腚メ 2021-10-19 08:46 329阅读 0赞

## 题目描述 ##

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路：  
  首先对于一个数来说我们要考虑要不要把它归入到最大连续和的子序列中，这其中的判断依据是什么？难道只是一个数是否小于0？不，不然，对于最大连续和的子序列，我们允许它其中是有负数的，我们这里考虑的是这个数对于这个最大连续和的子序列的影响，如果我加上这个数了，那么这个最大连续和的子序列小于0了，那么我认为这个数以及这个数之前的序列都是不可取的，是呈现负增长的，我会重新规划这个最大子序列的；如果加上这个数，这个最大连续子序列的和不为0，那么我认为，这个数以及之前的序列是可取的，对于和来说是呈现一种正增长的。

class Solution {
        public int maxSubArray(int[] nums) {
            int result = nums[0];
            int sum = 0;
            for (int m:nums){
                // 如果是大于0那么这个数就是具有递增意义的数
                if (sum > 0) {
                    sum += m;
                }else {
                    // 如果是小于0就是递减的作用
                    sum = m;
                }
                // 这一步是求最大子序和的关键，得到那个最大值，保存着
                result = Math.max(result,sum);
            }
            return result;
        }
    }

## 结果： ##

![\[图片\]][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTAxMTA1_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTAxMTA1_size_16_color_FFFFFF_t_70]: /images/20211018/034a5b6344d344008506d5d83c1e333e.png