[백준] 2559번 : 수열 | C++

문제 : https://www.acmicpc.net/problem/2559

 

풀이 로직 :

1. 부분합을 생각하기

2. 반복문 시작을 0이 아닌 1로 하기

3. 최대 최솟값 찾는 방법 2가지

    a) max_element(배열 시작, 배열 종료) -> 전체 비교할 값을 배열에 넣어두고, 마지막에 한번에 찾는다

    b) max(현재 최대값, 새로운 값) -> 반복문을 돌면서 계속 최댓값을 갱신해나가는 방법. 이를 위해선 (최대값 찾는 경우니까)가능한 가장 최소값을 초기값으로 둔 후, 최대값을 찾아나서야 한다.

#include<bits/stdc++.h>

using namespace std;

int n,k; //전체 날짜 개수, 연속날짜 개수
int v[100000];
int sum[100000]; //각 자리까지의 합을 더해서 저장

vector<int> sumK;
int ans = -10000000;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>k;

    for(int i=0; i<n; i++){
        cin >> v[i];
        if(i==0){
        //i=1부터 시작하여 i<=n 으로 범위를 설정하면 따로 i==0인 경우의 sum값을 제외하는 과정 안거쳐도 된다
            sum[i]=v[i];        
            }else{
            sum[i]=sum[i-1]+v[i];
        }
    }
    
    ans = max(sum[k-1],ans);
    for(int i=k;i<n;i++){
        ans= max(sum[i]-sum[i-k], ans);
    }
    cout <<ans;

    sumK.push_back(sum[k-1]);//하나씩 넣은 후에, 그 배열 전체에서 멕스값 찾는 방법 

    for(int i=k; i<n; i++){
        int curSum = sum[i]-sum[i-k];
        sumK.push_back(curSum);
    }

    cout << *max_element(sumK.begin(),sumK.end());

    // 하나씩 비교하며 실시간으로 멕스값 업데이트 하는 방법 -> 초기 멕스값은 최소 숫자로 둬야함 
    // 최소숫자 찾는 방법
    // int min = -10000000;
}