👀 문제
https://leetcode.com/problems/maximum-subarray/
👊 도전
1. 설계
- DP를 이용한다.
- 누적합에 i값을 더할 지, 아니면 i값에서부터 다시 시작할 지 둘 중 max로 결정한다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
*
* @author HEESOO
*
*/
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length==1) return nums[0];
int n=nums.length;
long[] dp=new long[n];
long answer=nums[0]; // dp에서 최댓값을 저장
dp[0]=nums[0];
for(int i=1;i<n;i++){
dp[i]=Math.max(dp[i-1]+nums[i], nums[i]); // i를 더하거나, i에서 다시 시작하거나
answer=Math.max(answer, dp[i]);
}
System.out.println(Arrays.toString(dp));
return (int)answer;
}
}
3. 결과
🤟 성공 🤟
answer을 dp[0]이 아닌 Integer.MIN으로 초기화해서 실패했다. [-1,-2]인 경우 answer에 -1이 들어가지 않기 때문이다.
4. 설명
- DP를 이용한다
- dp[i]=Math.max(dp[i-1]+nums[i], nums[i])
- dp[i]: i번째까지의 누적 합
- 이전 합에서 nums[i]를 더한 것과, nums[i] 자체 중 더 큰 값을 설정한다. nums[i]를 선택하게 되면, i부터 누적합을 다시 구하는 것이다.
- dp 마지막 인덱스에 누적 값의 최댓값이 들어온다는 보장은 없으므로, answer을 두어 dp의 최댓값을 저장한다.
- nums[i]의 범위가 int형 범위와 같고, 합을 구하는 문제이기 때문에 오버플로우를 생각하여 dp를 long형으로 선언했다.
- 근데 문제는 여기까지 의도한게 맞는건지 모르겠지만, 리턴형이 int여서 마지막에 answer를 int로 형변환하였다.