문제 링크

내 코드

Solution 참고.

Solution

Approach 1: Memoization

• 31ms, 35.02MB
• Complexity
  • Let $n$ be the length of the input array nums, $k$ be the length of each subarray and $m$ be the required number of non-overlapping subarrays.
  • Time Complexity: $O(n \cdot m) \approx O(n)$
  • Space Complexity: $O(n \cdot m) \approx O(n)$

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        // Number of possible subarray starting positions
        int n = nums.size() - k + 1;

        // Calculate sum of all possible k-length subarrays
        vector<int> sums(n);
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        sums[0] = windowSum;

        // Sliding window to calculate remaining sums
        for (int i = k; i < nums.size(); i++) {
            windowSum = windowSum - nums[i - k] + nums[i];
            sums[i - k + 1] = windowSum;
        }

        // memo[i][j]: max sum possible starting from index i with j subarrays
        // remaining
        vector<vector<int>> memo(n, vector<int>(4, -1));
        vector<int> indices;

        // First find optimal sum using DP
        dp(sums, k, 0, 3, memo);

        // Then reconstruct the path to find indices
        dfs(sums, k, 0, 3, memo, indices);

        return indices;
    }

private:
    // DP function to find maximum possible sum
    int dp(vector<int>& sums, int k, int idx, int rem,
           vector<vector<int>>& memo) {
        if (rem == 0) return 0;
        if (idx >= sums.size()) {
            return rem > 0 ? INT_MIN : 0;
        }

        if (memo[idx][rem] != -1) {
            return memo[idx][rem];
        }

        // Try taking current subarray vs skipping it
        int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
        int skipCurrent = dp(sums, k, idx + 1, rem, memo);

        memo[idx][rem] = max(withCurrent, skipCurrent);
        return memo[idx][rem];
    }

    // DFS to reconstruct the solution path
    void dfs(vector<int>& sums, int k, int idx, int rem,
             vector<vector<int>>& memo, vector<int>& indices) {
        if (rem == 0) return;
        if (idx >= sums.size()) return;

        int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
        int skipCurrent = dp(sums, k, idx + 1, rem, memo);

        // Choose path that gave optimal result in DP
        if (withCurrent >= skipCurrent) {  // Take current subarray
            indices.push_back(idx);
            dfs(sums, k, idx + k, rem - 1, memo, indices);
        } else {  // Skip current subarray
            dfs(sums, k, idx + 1, rem, memo, indices);
        }
    }
};

GPT

이 코드는 배열 nums에서 서로 겹치지 않는 세 개의 부분 배열을 선택하여 합계를 최대화하는 문제를 해결합니다. 각 부분 배열의 길이는 $k$로 고정되어 있습니다. 문제는 동적 프로그래밍(DP)과 메모이제이션을 사용해 효율적으로 해결됩니다.

---

코드 설명

1. 주요 아이디어

• $n = \text{nums.size()} - k + 1$: 가능한 $k$-길이 부분 배열의 시작 인덱스 수입니다.
• sums: 배열의 각 $k$-길이 부분 배열의 합을 저장합니다.
  • 예: nums = [1, 2, 3, 4, 5], $k = 2$이면 sums = [3, 5, 7, 9] (각각 $[1+2, 2+3, 3+4, 4+5]$).
• 동적 프로그래밍으로:
  • dp(i, rem): 인덱스 $i$에서 시작해 $rem$개의 부분 배열을 선택할 때의 최대 합.
  • 메모이제이션으로 중복 계산을 방지.
• 최적의 선택 경로를 재구성하여 인덱스를 반환합니다.

---

2. maxSumOfThreeSubarrays 함수

a. $k$-길이 부분 배열의 합 계산

vector<int> sums(n);
int windowSum = 0;
for (int i = 0; i < k; i++) {
    windowSum += nums[i];
}
sums[0] = windowSum;

for (int i = k; i < nums.size(); i++) {
    windowSum = windowSum - nums[i - k] + nums[i];
    sums[i - k + 1] = windowSum;
}

• 슬라이딩 윈도우 기법으로 배열의 모든 $k$-길이 부분 배열의 합을 계산해 sums 배열에 저장.
• 시간 복잡도: $O(n)$.

---

b. 동적 프로그래밍과 경로 추적

vector<vector<int>> memo(n, vector<int>(4, -1));
vector<int> indices;

// First find optimal sum using DP
dp(sums, k, 0, 3, memo);

// Then reconstruct the path to find indices
dfs(sums, k, 0, 3, memo, indices);

• memo: DP 결과를 저장하는 2차원 배열.
  • 행: 부분 배열의 시작 인덱스.
  • 열: 선택 가능한 부분 배열의 개수 ($0 \leq rem \leq 3$).
• 두 단계를 통해 문제를 해결:
  1. DP를 이용해 최대 합을 계산.
  2. DFS로 최적 경로를 재구성해 인덱스 반환.

---

3. DP 함수 (dp)

int dp(vector<int>& sums, int k, int idx, int rem, vector<vector<int>>& memo) {
    if (rem == 0) return 0;
    if (idx >= sums.size()) {
        return rem > 0 ? INT_MIN : 0;
    }

    if (memo[idx][rem] != -1) {
        return memo[idx][rem];
    }

    int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
    int skipCurrent = dp(sums, k, idx + 1, rem, memo);

    memo[idx][rem] = max(withCurrent, skipCurrent);
    return memo[idx][rem];
}

a. 기저 조건

1. 부분 배열을 모두 선택한 경우 (rem == 0):
   • 합계는 0.
2. 범위를 벗어난 경우:
   • 남은 부분 배열을 선택할 수 없으므로 결과는 INT_MIN.

b. 메모이제이션 확인

• memo[idx][rem]에 값이 저장되어 있다면 중복 계산을 방지하기 위해 해당 값을 반환.

c. 현재 부분 배열 선택 여부

1. 현재 부분 배열 선택 (withCurrent):
   • 합계에 sums[idx]를 더하고, 다음 가능한 시작 위치로 이동 ($idx + k$).
   • 남은 부분 배열 수는 $rem - 1$.
2. 현재 부분 배열 건너뛰기 (skipCurrent):
   • 다음 위치로 이동 ($idx + 1$).

d. 결과 저장 및 반환

• 현재 상태에서 최대 합을 계산하고 메모이제이션 테이블에 저장.

---

4. DFS 함수 (dfs)

void dfs(vector<int>& sums, int k, int idx, int rem, vector<vector<int>>& memo, vector<int>& indices) {
    if (rem == 0) return;
    if (idx >= sums.size()) return;

    int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
    int skipCurrent = dp(sums, k, idx + 1, rem, memo);

    if (withCurrent >= skipCurrent) {  // Take current subarray
        indices.push_back(idx);
        dfs(sums, k, idx + k, rem - 1, memo, indices);
    } else {  // Skip current subarray
        dfs(sums, k, idx + 1, rem, memo, indices);
    }
}

작동 원리

• DP 결과를 기반으로 최적 경로를 추적.
• 현재 부분 배열을 선택하거나 건너뛰며 선택한 인덱스를 indices에 추가.

---

시간 및 공간 복잡도

시간 복잡도

1. 슬라이딩 윈도우 합 계산: $O(n)$.
2. DP 함수: 각 상태는 한 번만 계산되므로 $O(n \times 3) = O(n)$.
3. DFS 경로 추적: $O(n)$.

총 시간 복잡도: $O(n)$.

공간 복잡도

1. memo 배열: $O(n \times 4) = O(n)$.
2. sums 배열: $O(n)$.

총 공간 복잡도: $O(n)$.

---

작동 예시

입력:

nums = [1, 2, 1, 2, 6, 7, 5, 1]
k = 2

계산 과정:

1. sums 배열: $[3, 3, 3, 8, 13, 12, 6]$
   (부분 배열 합계: $[1+2, 2+1, 1+2, 2+6, 6+7, 7+5, 5+1]$).

2. DP 결과:

   • 최대 합: $16$ (인덱스 $[0, 3, 5]$).

3. DFS 경로 추적:

   • 최적 인덱스: $[0, 3, 5]$.

출력:

[0, 3, 5]

Approach 2: Tabulation

• 7ms, 31.23MB
• Complexity
  • Let $n$ be the length of the input array nums, $k$ be the length of each subarray and $m$ be the required number of non-overlapping subarrays.
  • Time Complexity: $O(n \cdot m) \approx O(n)$
  • Space Complexity: $O(n \cdot m) \approx O(n)$

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();

        // Prefix sum array to calculate sum of any subarray in O(1) time
        vector<int> prefixSum(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }

        // Arrays to store the best sum and starting indices for up to 3
        // subarrays
        vector<vector<int>> bestSum(4, vector<int>(n + 1, 0));
        vector<vector<int>> bestIndex(4, vector<int>(n + 1, 0));

        // Compute the best sum and indices for 1, 2, and 3 subarrays
        for (int subarrayCount = 1; subarrayCount <= 3; subarrayCount++) {
            for (int endIndex = k * subarrayCount; endIndex <= n; endIndex++) {
                int currentSum = prefixSum[endIndex] - prefixSum[endIndex - k] +
                                 bestSum[subarrayCount - 1][endIndex - k];

                // Check if the current configuration gives a better sum
                if (currentSum > bestSum[subarrayCount][endIndex - 1]) {
                    bestSum[subarrayCount][endIndex] = currentSum;
                    bestIndex[subarrayCount][endIndex] = endIndex - k;
                } else {
                    bestSum[subarrayCount][endIndex] =
                        bestSum[subarrayCount][endIndex - 1];
                    bestIndex[subarrayCount][endIndex] =
                        bestIndex[subarrayCount][endIndex - 1];
                }
            }
        }

        // Trace back the indices of the three subarrays
        vector<int> result(3, 0);
        int currentEnd = n;
        for (int subarrayIndex = 3; subarrayIndex >= 1; subarrayIndex--) {
            result[subarrayIndex - 1] = bestIndex[subarrayIndex][currentEnd];
            currentEnd = result[subarrayIndex - 1];
        }

        return result;
    }
};

GPT

이 코드는 배열 nums에서 겹치지 않는 세 개의 부분 배열을 선택하여 합계를 최대화하는 문제를 해결합니다. 각 부분 배열의 길이는 $k$로 고정되어 있으며, 동적 프로그래밍(DP) 을 사용해 효율적으로 문제를 해결합니다.

---

코드 설명

1. 주요 아이디어

• prefixSum:
  • 부분 합(prefix sum)을 사용해 $[l, r]$ 범위의 합을 $O(1)$로 계산.
  • $\text{prefixSum}[r+1] - \text{prefixSum}[l]$로 $[l, r]$ 범위 합을 구함.
• bestSum:
  • bestSum[subarrayCount][endIndex]: $subarrayCount$개의 부분 배열을 사용하고, 마지막 부분 배열의 끝 인덱스가 $endIndex$일 때의 최대 합.
• bestIndex:
  • bestIndex[subarrayCount][endIndex]: 위 경우의 최적 부분 배열 시작 인덱스를 저장.

---

코드 세부 사항

1. Prefix Sum 계산

vector<int> prefixSum(n + 1, 0);
for (int i = 1; i <= n; i++) {
    prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
}

• $O(n)$ 시간 복잡도로 배열의 부분 합(prefix sum)을 계산.
• 예: nums = [1, 2, 3, 4]이면 prefixSum = [0, 1, 3, 6, 10].

---

2. DP 테이블 초기화

vector<vector<int>> bestSum(4, vector<int>(n + 1, 0));
vector<vector<int>> bestIndex(4, vector<int>(n + 1, 0));

• bestSum: 최대 합을 저장하는 DP 테이블.
• bestIndex: 최적 시작 인덱스를 저장하는 테이블.

---

3. DP를 통해 최대 합 계산

for (int subarrayCount = 1; subarrayCount <= 3; subarrayCount++) {
    for (int endIndex = k * subarrayCount; endIndex <= n; endIndex++) {
        int currentSum = prefixSum[endIndex] - prefixSum[endIndex - k] +
                         bestSum[subarrayCount - 1][endIndex - k];

a. $k$-길이 부분 배열 합 계산

• 현재 부분 배열의 끝 인덱스가 $endIndex$일 때: $\text{currentSum} = \text{prefixSum}[endIndex] - \text{prefixSum}[endIndex - k]$
  • 이는 $[endIndex-k, endIndex)$ 부분 배열의 합을 계산.
  • 이전까지의 최적 결과($subarrayCount - 1$)를 더함.

b. 최적 결과 갱신

if (currentSum > bestSum[subarrayCount][endIndex - 1]) {
    bestSum[subarrayCount][endIndex] = currentSum;
    bestIndex[subarrayCount][endIndex] = endIndex - k;
} else {
    bestSum[subarrayCount][endIndex] = bestSum[subarrayCount][endIndex - 1];
    bestIndex[subarrayCount][endIndex] = bestIndex[subarrayCount][endIndex - 1];
}

• $currentSum$이 이전 최대값보다 크면 갱신.
• 이전 값을 유지하거나 현재 값을 선택.

---

4. 최적 경로 추적

vector<int> result(3, 0);
int currentEnd = n;
for (int subarrayIndex = 3; subarrayIndex >= 1; subarrayIndex--) {
    result[subarrayIndex - 1] = bestIndex[subarrayIndex][currentEnd];
    currentEnd = result[subarrayIndex - 1];
}

• DP 테이블 bestIndex를 역순으로 추적해 최적의 세 부분 배열 시작 인덱스를 찾음.
• 결과를 저장하여 반환.

---

시간 및 공간 복잡도

시간 복잡도

1. Prefix Sum 계산: $O(n)$
2. DP 테이블 계산: $O(3 \times n) = O(n)$
   • $3$은 최대 $3$개의 부분 배열을 선택하기 때문.
3. 최적 경로 추적: $O(3) = O(1)$

총 시간 복잡도: $O(n)$.

공간 복잡도

1. prefixSum: $O(n)$
2. bestSum 및 bestIndex: $O(4 \times n) = O(n)$

총 공간 복잡도: $O(n)$.

---

작동 예시

입력:

nums = [1, 2, 1, 2, 6, 7, 5, 1], k = 2

계산 과정:

1. Prefix Sum: $\text{prefixSum} = [0, 1, 3, 4, 6, 12, 19, 24, 25]$

2. DP 테이블 계산:

$subarrayCount$	$endIndex = 2$	$endIndex = 3$	$endIndex = 4$	…	$endIndex = 8$
1	$3$	$3$	$3$	…	$13$
2	N/A	N/A	$8$	…	$20$
3	N/A	N/A	N/A	…	$25$

3. 최적 경로 추적:
   • 결과: $[0, 3, 5]$

출력:

[0, 3, 5]

Approach 3: Three Pointers

• 4ms, 26.42MB
• Complexity
  • Let $n$ be the length of the input array nums.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        int maxSum = 0;

        // Prefix sum array to calculate sum of any subarray
        vector<int> prefixSum(n + 1);
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        // Arrays to store the best starting index for the left and right
        // subarrays
        vector<int> leftMaxIndex(n);
        vector<int> rightMaxIndex(n);

        // Result array to store the starting indices of the three subarrays
        vector<int> result(3);

        // Calculate the best starting index for the left subarray for each
        // position
        for (int i = k, currentMaxSum = prefixSum[k] - prefixSum[0]; i < n;
             i++) {
            if (prefixSum[i + 1] - prefixSum[i + 1 - k] > currentMaxSum) {
                leftMaxIndex[i] = i + 1 - k;
                currentMaxSum = prefixSum[i + 1] - prefixSum[i + 1 - k];
            } else {
                leftMaxIndex[i] = leftMaxIndex[i - 1];
            }
        }

        // Calculate the best starting index for the right subarray for each
        // position
        rightMaxIndex[n - k] = n - k;
        for (int i = n - k - 1, currentMaxSum = prefixSum[n] - prefixSum[n - k];
             i >= 0; i--) {
            if (prefixSum[i + k] - prefixSum[i] >= currentMaxSum) {
                rightMaxIndex[i] = i;
                currentMaxSum = prefixSum[i + k] - prefixSum[i];
            } else {
                rightMaxIndex[i] = rightMaxIndex[i + 1];
            }
        }

        // Iterate over the middle subarray and calculate the total sum for all
        // valid combinations
        for (int i = k; i <= n - 2 * k; i++) {
            int leftIndex = leftMaxIndex[i - 1];
            int rightIndex = rightMaxIndex[i + k];
            int totalSum = (prefixSum[i + k] - prefixSum[i]) +
                           (prefixSum[leftIndex + k] - prefixSum[leftIndex]) +
                           (prefixSum[rightIndex + k] - prefixSum[rightIndex]);

            if (totalSum > maxSum) {
                maxSum = totalSum;
                result[0] = leftIndex;
                result[1] = i;
                result[2] = rightIndex;
            }
        }

        return result;
    }
};

GPT

이 코드는 배열 nums에서 길이가 $k$인 서로 겹치지 않는 세 개의 부분 배열을 선택하여 합계를 최대화하는 문제를 해결합니다. 세 부분 배열의 시작 인덱스를 반환합니다. 아래는 코드의 상세 설명입니다.

---

코드 분석

1. 주요 아이디어

• prefixSum:
  • 부분 합(prefix sum)을 사용하여 $[l, r]$ 범위의 합을 $O(1)$로 계산.
  • $\text{prefixSum}[r+1] - \text{prefixSum}[l]$로 $[l, r]$의 합 계산.
• leftMaxIndex:
  • 각 인덱스에서 왼쪽 부분 배열의 최적 시작 인덱스를 추적.
• rightMaxIndex:
  • 각 인덱스에서 오른쪽 부분 배열의 최적 시작 인덱스를 추적.

전체적으로:

1. 왼쪽과 오른쪽 최적의 부분 배열 시작 인덱스를 미리 계산.
2. 중간 부분 배열을 순회하며 최대 합계를 계산.

---

2. Prefix Sum 계산

vector<int> prefixSum(n + 1);
for (int i = 0; i < n; i++) {
    prefixSum[i + 1] = prefixSum[i] + nums[i];
}

• prefixSum: 누적 합을 계산해 각 부분 배열의 합을 빠르게 계산.
• 예: nums = [1, 2, 3, 4]이면 prefixSum = [0, 1, 3, 6, 10].
• $[l, r]$의 합은 $\text{prefixSum}[r+1] - \text{prefixSum}[l]$.

---

3. 왼쪽 부분 배열 최적화 (leftMaxIndex)

for (int i = k, currentMaxSum = prefixSum[k] - prefixSum[0]; i < n; i++) {
    if (prefixSum[i + 1] - prefixSum[i + 1 - k] > currentMaxSum) {
        leftMaxIndex[i] = i + 1 - k;
        currentMaxSum = prefixSum[i + 1] - prefixSum[i + 1 - k];
    } else {
        leftMaxIndex[i] = leftMaxIndex[i - 1];
    }
}

• 목적: 각 인덱스 $i$에서 왼쪽 부분 배열의 최적 시작 인덱스를 계산.

• $currentMaxSum$: 현재까지의 최대 합.

• $\text{prefixSum}[i+1] - \text{prefixSum}[i+1-k]$: $[i-k+1, i]$ 부분 배열의 합.

• 갱신:

  • 현재 부분 배열의 합이 더 크다면 leftMaxIndex[i]를 갱신.
  • 그렇지 않으면 이전 최적 인덱스를 복사.

---

4. 오른쪽 부분 배열 최적화 (rightMaxIndex)

rightMaxIndex[n - k] = n - k;
for (int i = n - k - 1, currentMaxSum = prefixSum[n] - prefixSum[n - k];
     i >= 0; i--) {
    if (prefixSum[i + k] - prefixSum[i] >= currentMaxSum) {
        rightMaxIndex[i] = i;
        currentMaxSum = prefixSum[i + k] - prefixSum[i];
    } else {
        rightMaxIndex[i] = rightMaxIndex[i + 1];
    }
}

• 목적: 각 인덱스 $i$에서 오른쪽 부분 배열의 최적 시작 인덱스를 계산.

• $currentMaxSum$: 현재까지의 최대 합.

• $\text{prefixSum}[i+k] - \text{prefixSum}[i]$: $[i, i+k-1]$ 부분 배열의 합.

• 갱신:

  • 현재 부분 배열의 합이 더 크거나 같다면 rightMaxIndex[i]를 갱신.
  • 그렇지 않으면 다음 인덱스의 최적 인덱스를 복사.

---

5. 중간 부분 배열 순회 및 최대 합 계산

for (int i = k; i <= n - 2 * k; i++) {
    int leftIndex = leftMaxIndex[i - 1];
    int rightIndex = rightMaxIndex[i + k];
    int totalSum = (prefixSum[i + k] - prefixSum[i]) +
                   (prefixSum[leftIndex + k] - prefixSum[leftIndex]) +
                   (prefixSum[rightIndex + k] - prefixSum[rightIndex]);

    if (totalSum > maxSum) {
        maxSum = totalSum;
        result[0] = leftIndex;
        result[1] = i;
        result[2] = rightIndex;
    }
}

• 목적: 중간 부분 배열의 시작 인덱스를 순회하며 세 부분 배열의 최대 합을 계산.

• $i$: 중간 부분 배열의 시작 인덱스.

• leftIndex: $i-1$까지의 최적 왼쪽 부분 배열 시작 인덱스.

• rightIndex: $i+k$부터의 최적 오른쪽 부분 배열 시작 인덱스.

• totalSum: 세 부분 배열의 합.

• 최적 합 갱신:

  • totalSum이 더 크면 maxSum과 result를 갱신.

---

시간 및 공간 복잡도

시간 복잡도

1. Prefix Sum 계산: $O(n)$
2. leftMaxIndex와 rightMaxIndex 계산: 각각 $O(n)$
3. 중간 부분 배열 순회: $O(n)$

총 시간 복잡도: $O(n)$.

공간 복잡도

1. prefixSum: $O(n)$
2. leftMaxIndex와 rightMaxIndex: $O(n)$
3. 결과 저장 공간: $O(1)$

총 공간 복잡도: $O(n)$.

---

작동 예시

입력:

nums = [1, 2, 1, 2, 6, 7, 5, 1], k = 2

계산 과정:

1. Prefix Sum: $\text{prefixSum} = [0, 1, 3, 4, 6, 12, 19, 24, 25]$

2. leftMaxIndex 계산: $\text{leftMaxIndex} = [0, 0, 0, 1, 3, 3, 3, 3]$

3. rightMaxIndex 계산: $\text{rightMaxIndex} = [4, 4, 4, 4, 4, 5, 6, 7]$

4. 중간 부분 배열 순회:

   • $i = 2$: 합계 $3 + 8 + 13 = 24$
   • $i = 3$: 합계 $3 + 8 + 12 = 23$
   • $i = 4$: 합계 $5 + 13 + 12 = 30$

출력:

[0, 3, 5]

Approach 4: Sliding Window

• 0ms, 23.98MB
• Complexity
  • Let $n$ be the length of the input array nums.
  • Time Complexity: $O(n + k)$
  • Space Complexity: $O(1)$

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        // Variables to track the best indices for one, two, and three subarray
        // configurations
        int bestSingleStart = 0;
        vector<int> bestDoubleStart = {0, k};
        vector<int> bestTripleStart = {0, k, k * 2};

        // Compute the initial sums for the first three subarrays
        int currentWindowSumSingle = 0;
        for (int i = 0; i < k; i++) {
            currentWindowSumSingle += nums[i];
        }

        int currentWindowSumDouble = 0;
        for (int i = k; i < k * 2; i++) {
            currentWindowSumDouble += nums[i];
        }

        int currentWindowSumTriple = 0;
        for (int i = k * 2; i < k * 3; i++) {
            currentWindowSumTriple += nums[i];
        }

        // Track the best sums found so far
        int bestSingleSum = currentWindowSumSingle;
        int bestDoubleSum = currentWindowSumSingle + currentWindowSumDouble;
        int bestTripleSum = currentWindowSumSingle + currentWindowSumDouble +
                            currentWindowSumTriple;

        // Sliding window pointers for the subarrays
        int singleStartIndex = 1;
        int doubleStartIndex = k + 1;
        int tripleStartIndex = k * 2 + 1;

        // Slide the windows across the array
        while (tripleStartIndex <= nums.size() - k) {
            // Update the sums using the sliding window technique
            currentWindowSumSingle = currentWindowSumSingle -
                                     nums[singleStartIndex - 1] +
                                     nums[singleStartIndex + k - 1];
            currentWindowSumDouble = currentWindowSumDouble -
                                     nums[doubleStartIndex - 1] +
                                     nums[doubleStartIndex + k - 1];
            currentWindowSumTriple = currentWindowSumTriple -
                                     nums[tripleStartIndex - 1] +
                                     nums[tripleStartIndex + k - 1];

            // Update the best single subarray start index if a better sum is
            // found
            if (currentWindowSumSingle > bestSingleSum) {
                bestSingleStart = singleStartIndex;
                bestSingleSum = currentWindowSumSingle;
            }

            // Update the best double subarray start indices if a better sum is
            // found
            if (currentWindowSumDouble + bestSingleSum > bestDoubleSum) {
                bestDoubleStart[0] = bestSingleStart;
                bestDoubleStart[1] = doubleStartIndex;
                bestDoubleSum = currentWindowSumDouble + bestSingleSum;
            }

            // Update the best triple subarray start indices if a better sum is
            // found
            if (currentWindowSumTriple + bestDoubleSum > bestTripleSum) {
                bestTripleStart[0] = bestDoubleStart[0];
                bestTripleStart[1] = bestDoubleStart[1];
                bestTripleStart[2] = tripleStartIndex;
                bestTripleSum = currentWindowSumTriple + bestDoubleSum;
            }

            // Move the sliding windows forward
            singleStartIndex += 1;
            doubleStartIndex += 1;
            tripleStartIndex += 1;
        }

        // Return the starting indices of the three subarrays with the maximum
        // sum
        return bestTripleStart;
    }
};

GPT

이 코드는 배열 nums에서 길이가 $k$인 서로 겹치지 않는 세 개의 부분 배열을 선택하여 합계를 최대화하는 문제를 해결합니다. 각 부분 배열의 시작 인덱스를 반환하며, 슬라이딩 윈도우 기법을 사용해 효율적으로 문제를 해결합니다.

---

코드 분석

1. 주요 아이디어

• 슬라이딩 윈도우:
  • $k$-길이의 부분 배열 합계를 슬라이딩 윈도우 방식으로 업데이트.
  • 한 번의 배열 순회로 모든 $k$-길이 부분 배열의 합을 계산.
• 단일, 이중, 삼중 부분 배열 추적:
  • 각각의 윈도우 합계와 최적의 시작 인덱스를 유지하며, 최적화된 경로를 따라 이동.

---

코드 단계별 설명

1. 초기화

int bestSingleStart = 0;
vector<int> bestDoubleStart = {0, k};
vector<int> bestTripleStart = {0, k, k * 2};

• bestSingleStart: 단일 $k$-길이 부분 배열의 최적 시작 인덱스.
• bestDoubleStart: 두 개의 $k$-길이 부분 배열의 최적 시작 인덱스 배열.
• bestTripleStart: 세 개의 $k$-길이 부분 배열의 최적 시작 인덱스 배열.

---

2. 초기 부분 배열 합 계산

int currentWindowSumSingle = 0;
for (int i = 0; i < k; i++) {
    currentWindowSumSingle += nums[i];
}

• 첫 번째 $k$-길이 부분 배열의 합을 계산.

int currentWindowSumDouble = 0;
for (int i = k; i < k * 2; i++) {
    currentWindowSumDouble += nums[i];
}

• 두 번째 $k$-길이 부분 배열의 합을 계산.

int currentWindowSumTriple = 0;
for (int i = k * 2; i < k * 3; i++) {
    currentWindowSumTriple += nums[i];
}

• 세 번째 $k$-길이 부분 배열의 합을 계산.

---

3. 최적합 초기화

int bestSingleSum = currentWindowSumSingle;
int bestDoubleSum = currentWindowSumSingle + currentWindowSumDouble;
int bestTripleSum = currentWindowSumSingle + currentWindowSumDouble +
                    currentWindowSumTriple;

• 최적 단일, 이중, 삼중 $k$-길이 부분 배열의 합을 초기화.

---

4. 슬라이딩 윈도우 구현

int singleStartIndex = 1;
int doubleStartIndex = k + 1;
int tripleStartIndex = k * 2 + 1;

• 각 $k$-길이 윈도우의 시작 인덱스를 초기화.

while (tripleStartIndex <= nums.size() - k) {
    // Update the sums using the sliding window technique
    currentWindowSumSingle = currentWindowSumSingle -
                             nums[singleStartIndex - 1] +
                             nums[singleStartIndex + k - 1];
    currentWindowSumDouble = currentWindowSumDouble -
                             nums[doubleStartIndex - 1] +
                             nums[doubleStartIndex + k - 1];
    currentWindowSumTriple = currentWindowSumTriple -
                             nums[tripleStartIndex - 1] +
                             nums[tripleStartIndex + k - 1];

• 각 $k$-길이 부분 배열의 합을 슬라이딩 윈도우 방식으로 갱신.

a. 단일 부분 배열 최적합 갱신

if (currentWindowSumSingle > bestSingleSum) {
    bestSingleStart = singleStartIndex;
    bestSingleSum = currentWindowSumSingle;
}

• 현재 단일 부분 배열 합이 최적합보다 크면 갱신.

b. 이중 부분 배열 최적합 갱신

if (currentWindowSumDouble + bestSingleSum > bestDoubleSum) {
    bestDoubleStart[0] = bestSingleStart;
    bestDoubleStart[1] = doubleStartIndex;
    bestDoubleSum = currentWindowSumDouble + bestSingleSum;
}

• 현재 이중 부분 배열 합이 최적합보다 크면 갱신.

c. 삼중 부분 배열 최적합 갱신

if (currentWindowSumTriple + bestDoubleSum > bestTripleSum) {
    bestTripleStart[0] = bestDoubleStart[0];
    bestTripleStart[1] = bestDoubleStart[1];
    bestTripleStart[2] = tripleStartIndex;
    bestTripleSum = currentWindowSumTriple + bestDoubleSum;
}

• 현재 삼중 부분 배열 합이 최적합보다 크면 갱신.

d. 윈도우 이동

singleStartIndex += 1;
doubleStartIndex += 1;
tripleStartIndex += 1;

• 모든 윈도우를 한 칸씩 이동.

---

5. 결과 반환

return bestTripleStart;

• 최적의 세 부분 배열 시작 인덱스를 반환.

---

시간 및 공간 복잡도

시간 복잡도

1. 초기 합 계산: $O(k)$ (각 윈도우의 첫 합 계산).
2. 슬라이딩 윈도우 계산: $O(n - 3k)$.
   • $n$: 배열 크기.
   • $k$: 부분 배열 길이.

총 시간 복잡도: $O(n)$.

공간 복잡도

• $O(1)$: 추가 배열 없이 상수 공간만 사용.

---

작동 예시

입력:

nums = [1, 2, 1, 2, 6, 7, 5, 1], k = 2

계산 과정:

1. 초기 합 계산:

   • 첫 번째 부분 배열 합: $3$ ($[1, 2]$).
   • 두 번째 부분 배열 합: $3$ ($[1, 2]$).
   • 세 번째 부분 배열 합: $13$ ($[6, 7]$).

2. 슬라이딩 윈도우:

   • $i = 3$: 갱신된 합계와 최적합 계산.
   • $i = 4$: …
   • $i = 5$: …

3. 결과:

   • 최적 인덱스: $[0, 3, 5]$.

출력:

[0, 3, 5]