다이나믹 프로그래밍

1. 하나의 문제를 서브 문제들로 나눌 수 있고 그 서브 문제들로 하나의 문제를 표현할 수 있을 때
2. 서브 문제의 값으로 큰문제의 값을 구할 수 있는가

LeetCode

max sub array

value 배열

start index 배열

점화식 : f(n) = max(f(n-1) + arr[n], arr[n])

f(n) : 현재 요소가 들어간 맥스값

max 곱하기 sub array

min 배열

max 배열

start index 배열 [ [min 시작 인덱스, max 시작 인덱스] , … ]

점화식: maxF(n) = max( maxF(n-1)*arr[n], minF(n-1) * arr[n], arr[n]

점화식: minF(n) = min( maxF(n-1)*arr[n], minF(n-1) * arr[n], arr[n]