O(n²) Brute Force를 O(n) One Pass로 최적화한 효율적 수익 계산 설계

Context

배열 내 최저가 매수와 최고가 매도 시점을 찾는 알고리즘 설계 과정. 중첩 루프를 사용하는 초기 접근 방식의 시간 복잡도 증가로 인한 대규모 데이터 처리 한계 발생.

Technical Solution

• 전수 조사를 통한 모든 조합 계산 방식의 O(n²) 시간 복잡도 제거
• 단일 루프 내에서 실시간 최솟값을 갱신하는 One Pass 전략 채택
• current_price와 minPrice의 차이를 이용한 즉각적인 profit 계산 로직 구현
• 별도의 추가 메모리 할당 없이 변수 두 개만 사용하는 Space Complexity O(1) 유지
• 매 시점 최적의 이익을 maxProfit에 업데이트하는 그리디 알고리즘 적용