13398 연속합 2

연속합 2 (13398)

 

풀이코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 13398 연속합 2

const int MAX = 100000;

int n;
int A[MAX + 1];
int cache[MAX + 1];
int cache2[MAX + 1];
int max(int a, int b){ return a > b ? a : b; }

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
    cin >> n;
	
    for(int i = 1; i <= n; i++){
        cin >> A[i];
    }
    
    cache[1] = A[1];
    cache2[1] = A[n];
	
	for(int i = 2; i <= n; i++){
		if(A[i] > cache[i - 1] + A[i]){
			cache[i] = A[i];
		}
		else{
			cache[i] = cache[i - 1] + A[i];
		}
    }
	
	for (int i = n; i>=1; i--) {
		cache2[i] = A[i];
        if (i == n) continue;
        if (cache2[i] < cache2[i+1] + A[i]) {
            cache2[i] = cache2[i+1] + A[i];
        }
    }
	
	
	int maxSum = cache[1];
	
	for(int i = 2; i <= n; i++){
		maxSum = maxSum > cache[i] ? maxSum : cache[i];
	}
	
	for(int i = 2; i < n; i++){
		maxSum = maxSum > cache[i - 1] + cache2[i + 1] ? maxSum : cache[i - 1] + cache2[i + 1];
	}
	
	cout << maxSum << '\n';
	
	

}

 

해설

---

적용한 레시피 / 방법론 + 접근법

1

풀이

1

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1