Leetcode刷题100天—53. 最大子序和(数组)—day22

客官°小女子只卖身不卖艺 2022-09-11 11:25 140阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210829235249630][]

#### [53. 最大子序和][53.] ####

难度简单3622收藏分享切换为英文接收动态反馈

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

**示例 1：**

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

**示例 2：**

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

**示例 3：**

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

**示例 4：**

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

**示例 5：**

输入：nums = [-100000]
    输出：-100000

**提示：**

*  `1 <= nums.length <= 3 * 104`
 *  `-105 <= nums[i] <= 105`

\*\*进阶：\*\*如果你已经实现复杂度为 `O(n)` 的解法，尝试使用更为精妙的 **分治法** 求解。

package 数组;
    
    public class _53_最大子序和 { 
        public int maxSubArray(int[] nums) { 
    //遍历一遍数组就知道了
        	int pre=0,maxnum=nums[0];
        	for(int num :nums){ 
        		pre=Math.max(pre+num, num);
    // 取出最大的值
        		maxnum=Math.max(maxnum, pre);
        	}
        	return maxnum;
        }
    }
    
    /* * 解析： [-2,1,-3,4,-1,2,1,-5,4] * 第一次遍历:num=-2 pre=-2 max=-2 * 第二次遍历:num=1 pre=1 max=1 * 第三次遍历: -3 -1 1 * 四 : 4 4 4 * 五 ： -1 3 max=4 * 六 ： 2 5 5 * 七 : 1 6 6 */

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210829235249630]: /images/20220828/55e7d2344a0b450c944cce14d116452d.png
[53.]: https://leetcode-cn.com/problems/maximum-subarray/