Problem Solving
[LeetCode] Maximum Subarray
luminous13
2022. 11. 6. 22:52
문제
첫 번째 접근: 완전탐색(Brute Force)
모든 subarray를 구해서 최댓값을 가지는 subarrayf를 구해보려했다.
하지만 시간초과가 났다. 데이터 크기가 10000이므로 O(N^2)에 해당하는 완탐은 시간 초과가 날 수 밖에 없다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public int maxSubArray(int[] nums) {
int answer = Integer.MIN_VALUE;
for (int s=0; s<nums.length; s++) {
int e = s;
int sum = 0;
while(e<nums.length) {
sum += nums[e];
answer = Math.max(answer, sum);
e++;
}
}
return answer;
}
}
|
cs |
두 번째 접근: DP(동적계획법)
동적계획법은 분할정복과 유사하다. 큰 문제를 풀기 위해 작은 문제를 푼 다음에 큰 문제의 답을 구한다.
여기서 작은 문제의 답을 저장했다가 더 큰 문제를 풀기 위해 작은 문제를 이용한다. 즉 동적계획법은 큰 문제 형식과 작은 문제 형식이 재귀적으로 연결되어있다.
dp[i]는 nums[i]로 끝나는 subarray의 최댓값이라고 하자.
그러면 DP 형식으로 식을 작성한다면 다음과 같이 작성할 수 있다.
maxSubArr(A,i) = A[i] + (maxSubArr(A, i-1) > 0 ? maxSubArr(A, i-1) : 0)
dp[i] = nums[i] + (dp[i-1] > 0 ? dp[i-1] : 0)
즉 더 작은 문제 dp[i-1]로 dp[i]를 구할 수 있고 결국 전체 배열에서 subarray의 최댓값을 구할 수 있다.
이 경우 시간복잡도는 배열을 한 번만 순회하므로 O(N)이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for (int i=1; i<n; i++) {
dp[i] = nums[i] + (dp[i-1] > 0 ? dp[i-1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
}
|
cs |