2866. Beautiful Towers II

• 시간 제한 내에 못 풀었던 문제. 쉽게 생각했으면 풀었을 것 같은데 너무 경우의 수를 더 잘 추려내려고 했던게 실수였던 것 같다.

• 2865. Beautiful Towers I와 똑같은 문제인데 array의 길이가 인 점이 다르다.
• 한마디로 말하면 전체 경우의 수를 다 시도해 볼 수 없다는 것이다.
• 모든 경우의 수를 다 시도하면 시간 제한에 걸린다.

• 따라서 전체 경우의 수 중 가능성 있는 index maxIndices 를 추려내야 한다.

• 결과값을 최대화 할 수 있는 후보 index는 maxHeights[index] 값이 peak가 되는 지점에 있는 모든 index에 해당된다.

• 높이의 변화 dir 를 추적하여 높이가 감소하고 있지 않은 상태 dir ≠ -1 → 감소하는 상태 dir = -1 로 변화하는 지점을 찾는다.

• 나머지 과정은 이전 문제와 동일하다.

class Solution {
public:
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        vector<int> maxIndices;
        int dir = 0, prev = 0;
        for (int i = 0; i < maxHeights.size(); ++i) {
            int curr = maxHeights[i];
            if (curr > prev) {
                dir = 1; 
            } else if (curr < prev) {
                if (dir != -1) maxIndices.push_back(i - 1);
                dir = -1;
            } else {
                dir = 0;
            }
            prev = curr;
        }
        if (dir != -1) maxIndices.push_back(maxHeights.size() - 1);
        
        long long maxSum = 0;
        for (auto maxIndex : maxIndices) {
            int maxHeight = maxHeights[maxIndex];
            long long sum = maxHeight;
            int curHeight = maxHeight;
            for (int i = maxIndex - 1; i >= 0; --i) {
                if (maxHeights[i] < curHeight) {
                    curHeight = maxHeights[i];
                }
                sum += curHeight;
            }
            curHeight = maxHeight;
            for (int i = maxIndex + 1; i < maxHeights.size(); ++i) {
                if (maxHeights[i] < curHeight) {
                    curHeight = maxHeights[i];
                }
                sum += curHeight;
            }
            if (sum > maxSum) maxSum = sum;
        }
        return maxSum;
    }
};