数组中最大子数组和之连续子数组和

数组中最大子数组和

前言一、案例

1、数组中最大子数组和2、示例二、题解1、暴力法2、利用已知条件 总结参考文献 前言

暴力解通常不能满足时间复杂度的要求，必须抓住已知条件来寻找低时间复杂度的解题方式。

一、案例 1、数组中最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

2、示例

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

二、题解 1、暴力法

直接以O(n2)的复杂度寻找最大和。

//最大子数组和public class MaxSubArray { public int maxSubArray(int[] nums) { //ON方复杂度来遍历出一个最大值 int max = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { int sum = nums[i]; if (max < sum) max = sum; for (int j = i + 1; j < nums.length; j++) { sum += nums[j]; if (max < sum) max = sum; } } return max; }

2、利用已知条件

连续子数组，有正有负，当左缀和小于等于0是就没有加下去的必要了，相当于把暴力法的第一层for往后面求和大于0的地方提，把暴力法的第二层for中的控制条件往前提到和小于等于0的地方。

//认真找出其中的规律和联系，不要被不严谨的我以为作为指导方针。 public int maxSubArray(int[] nums) { //当左缀和小等等于0时，左缀数组继续加下去没有意义，则需要定义新的起点，开始累加，把每向前遍历一步就作为一个终点，记录此时的和是否为最大值。 int res = nums[0]; int sum = 0; for (int num : nums) { sum += sum > 0 ? num : num - sum; res = res < sum ? sum : res; } return res; }

总结

1）利用已知的条件联系题解的方向做一个时间空间复杂度上的简化。
2）专注思考效率高，认真找出其中的规律和联系，不要被不严谨的我以为(不专注的体现)作为指导方针。
3）实在做不来(在专注思考的前提下)，看题解，此时不浪费宝贵的时间；也不要思考完了不上手敲代码，而直接去对题解，此时浪费题源。

参考文献

[1]LeetCode 原题