What is the best way to solve Partition into two subarrays?

The optimized O(n) approach using Greedy patterns is generally preferred.

경쟁 프로그래밍쉬움

두 개의 하위 배열로 분할

'두 개의 하위 배열로 분할' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

n 크기의 배열 arr과 정수 k을 사용하는 함수 max_difference_subarrays(arr, k)을 작성하세요. 선택한 요소의 합계와 나머지 n-k 요소의 합계 간의 절대 차이가 최대화되도록 arr에서 k 요소의 하위 집합을 선택하고 이 최대 절대 차이를 반환합니다.

제약

•1 <= k < len(arr) <= 10^5
•1 <= arr[i] <= 10^4

예

Example 1

Input

max_difference_subarrays([8, 4, 5, 2, 10], 2)

Output

Explanation

If we select the 2 smallest elements {2, 4} (sum 6), the remaining elements are {8, 5, 10} (sum 23). The difference is |23 - 6| = 17.

Example 2

Input

max_difference_subarrays([1, 1, 1, 1, 1], 3)

Output

Explanation

Select 3 elements (sum 3), remaining 2 sum to 2. The difference is 1.

Need a Hint?

세트나 힙과 같은 Greedy 관련 데이터 구조를 사용하는 것을 고려해보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

Greedy 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def min_diff_opt(arr):
    s = sum(arr); n = len(arr); dp = [[False]*(s+1) for _ in range(n+1)]
    for i in range(n+1): dp[i][0] = True
    for i in range(1, n+1):
        for j in range(1, s+1):
            if j < arr[i-1]: dp[i][j] = dp[i-1][j]
            else: dp[i][j] = dp[i-1][j] or dp[i-1][j-arr[i-1]]
    res = float('inf')
    for j in range(s // 2, -1, -1):
        if dp[n][j]: res = s - 2*j; break
    return res

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def min_diff_brute(arr):
    def solve(i, s1, s2):
        if i == len(arr): return abs(s1 - s2)
        return min(solve(i+1, s1+arr[i], s2), solve(i+1, s1, s2+arr[i]))
    return solve(0, 0, 0)