(Leetcode) 53 - Maximum Subarray
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/maximum-subarray/description
크게 어렵지 않은 문제인데 너무 복잡하게 생각해서 여러번 시도를 해야했던 문제이다.
모범답안
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
for (int i = 0; i < nums.length; i++) {
currentSum += nums[i];
maxSum = Math.max(maxSum, currentSum);
currentSum = Math.max(currentSum, 0);
}
return maxSum;
}
}
- currentSum이 maxSum보다 클 경우 maxSum을 갱신한다.
- currentSum은 음수일 경우 (0보다 작을 경우) 0으로 초기화 한다.
TC, SC
시간 복잡도는 O(n), 공간 복잡도는 O(1) 이다.