https://www.acmicpc.net/problem/10211
10211번: Maximum Subarray
크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있
www.acmicpc.net
- 접근 방법, 논리 흐름(알고리즘)
이 문제의 키워드는 "연속한" 부분 배열이라고 생각했다.
각 인덱스에서의 최댓값을 dp에 저장하는데, 만약 그 전 인덱스들의 합이 양수이면
전 배열들의 합과 해당하는 수의 합이 그 인덱스의 최댓값일 것이고,
전 인덱스들의 합이 음수이면
그냥 해당 인덱스의 값이 최댓값이 될 테니까 그대로 dp에 저장해준다.
- 풀이 코드
'백준 문제풀이' 카테고리의 다른 글
| [백준(BOJ)/C++] 1260번: DFS와 BFS - 코딩밥상 (0) | 2022.08.24 |
|---|---|
| [백준(BOJ)/C++] 1932번: 정수 삼각형 - 코딩밥상 (0) | 2022.08.16 |
| [백준(BOJ)/C++] 11726번: 2xn 타일링 - 코딩밥상 (0) | 2022.08.15 |
| [백준(BOJ)/C++] 18111번: 마인크래프트 - 코딩밥상 (0) | 2022.08.09 |
| [백준(BOJ)/C++] 14888번: 연산자 끼워넣기 - 코딩밥상 (0) | 2022.08.09 |
