Maximum Subarray
LeetCode https://leetcode.cn/problems/maximum-subarray/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length < 1) {
return 0;
}
int lastMax = 0;
int globalMax = nums[0];
for (int i = 0; i < nums.length; i++) {
lastMax = Math.max(nums[i], nums[i] + lastMax);
globalMax = Math.max(globalMax, lastMax);
}
return globalMax;
}
}
Complexity
- Time = O(n)
- Space = O(1)
This post is licensed under CC BY 4.0 by the author.