53. 最大子数组和

╰半夏微凉° 2024-04-01 15:00 37阅读 0赞

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

> 子数组:是数组中的一个连续部分。

##### 示例 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 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105  
 − 1 0 4 < = n u m s \[ i \] < = 1 0 4 -10^4 <= nums\[i\] <= 10^4 −104<=nums\[i\]<=104

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

#### 思路 ####

*  这道题用动态规划的思路并不难解决，比较难的是后文提出的用分治法求解，但由于其不是最优解法，所以先不列出来
 *  动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
 *  如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
 *  如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
 *  每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果

#### 代码： ####

public class max_sub_sum {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int [] sums = {
        5,4,-1,7,8};
    		System.out.println(maxSubArray(sums));
    
    	}
    	 public static int maxSubArray(int[] nums) {
        
    		 int ans = nums[0];
    		 int sum = 0;
    		 for(int num : nums) {
        
    			 if(sum > 0) {
        
    				 sum += num;
    			 }else {
        
    				 sum = num;
    			 }
    			 ans = Math.max(ans, sum);
    		 }
    		 return ans;
    	 }
    }

#### 复杂度分析： ####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

##### 注：仅供学习参考 #####

来源：[力扣][Link 1]

[Link 1]: https://leetcode.cn/problems/maximum-subarray/description/