Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 |
Tags
- 문제풀이
- Linux
- gradle
- leetcode
- OOM
- Go언어
- 리눅스
- redis
- 스칼라
- 알고리즘
- 주키퍼
- dynamic programming
- boj
- Java
- zookeeper
- docker
- 파이썬
- HBase
- 동적프로그래밍
- 프로그래머스
- 코드워
- DP
- 튜토리얼
- scala
- go
- golang
- Python
- 자바
- codewars
- programmers
Archives
- Today
- Total
목록2017/11/11 (1)
파이문
수열에서 연속된 구간의 최대 합 구하기
수열에서 연속된 구간의 최대 합 구하기Largest Sum Contiguous Subarray / Maximum subarray problem 유명한 문제로, 주어진 수열에서 최대 합을 구하는 것이 요점이다. 쉽게 생각하자면 O(n^2)으로 구하면 되지만 (Brute Force), 대부분의 문제 풀이 사이트에서는 O(n)으로 풀기를 권고하고 있다. 제일 무난 한것이 Dynamic Programming으로 푸는 것인데, Kadane’s Algorithm이라고 한다. 현재 까지의 구간의 최대 합과, 해당 숫자와 Max 값을 비교하고 이 값을 다시 전체 합과 Max 값을 비교하는 것이다.class Solution: def maxSubArray(self, nums): """ :type nums: List[int..
컴퓨터 과학/알고리즘
2017. 11. 11. 23:08