力扣53. 最大子数组和

Problem: 53. 最大子数组和

题目描述

思路及解法

1.为求出最大连续的子数组和,我们逻辑上假设有一个窗口在原数组上滑动,
欲求出最大连续,则需要保证窗口中的所有元素和最起码大于0;
2.即当当前窗口中的元素值的和小于0时,直接将其窗口舍弃,并在当前位置重新开一个新的窗口;
3.在实际操作中我们可以直接利用一个值(sum)进行累加操作,并判断其正负性;同时再记录一个值maxSum用于求出最大的连续子数组和

复杂度

时间复杂度:

$O(n)$;其中$n$为原数组$nums$的大小

空间复杂度:

$O(1)$

Code

public class Solution {/*** Slider windows* @param nums Given array* @return int*/public int maxSubArray(int[] nums) {int n = nums.length;int maxSum = Integer.MIN_VALUE;int sum = 0;for (int i = 0; i < n; ++i)  {if (sum < 0) {sum = 0;}sum += nums[i];if (sum > maxSum) {maxSum = sum;}}return maxSum;}
}