力扣53. 最大子数组和
Problem: 53. 最大子数组和
文章目录
- 题目描述
- 思路及解法
- 复杂度
- Code
题目描述
思路及解法
1.为求出最大连续的子数组和,我们逻辑上假设有一个窗口在原数组上滑动,
欲求出最大连续,则需要保证窗口中的所有元素和最起码大于0;
2.即当当前窗口中的元素值的和小于0时,直接将其窗口舍弃,并在当前位置重新开一个新的窗口;
3.在实际操作中我们可以直接利用一个值(sum)进行累加操作,并判断其正负性;同时再记录一个值maxSum用于求出最大的连续子数组和
复杂度
时间复杂度:
O
(
n
)
O(n)
O(n);其中
n
n
n为原数组
n
u
m
s
nums
nums的大小
空间复杂度:
O
(
1
)
O(1)
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;
}
}