#1912 연속합

https://www.acmicpc.net/problem/1912

1912번: 연속합

실버 2의 문제이다. 되게 쉽게 구현할 수 있었는데 나답지않게 문제풀다가 졸려가지고 중간에 샤워하고오고 이래서 좀 걸렸다. 반성해 나란 사람;

//2022-04-18 BOJ 1912
#include <iostream>
#include <algorithm>
using namespace std;

int n;
int dp[100001];
int arr[100001];

int main()
{
  //freopen("input.txt","r",stdin);
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  dp[0]=arr[0];
  int res=dp[0];

  for(int i=1;i<n;i++){
    dp[i]=max(dp[i-1]+arr[i],arr[i]);
    res=max(res,dp[i]);
  }

  cout<<res;
}

연속되는 수열이 주어진다. 이 수열의 앞에서부터 뒤의 수를 하나씩 더해간다. 더해가면서 수열의 값과 비교했을때 연속된 합이 작다면 수열의 값을 사용, 아니라면 연속된합을 계속 사용한다.

 

이것이 메인되는 아이디어이다.

i-1

i

 위와 같은 수열에서, 의사코드는 다음과 같다.

if(연속합< i번째 값)  i를 선택;

if(연속합> i번째 값)  연속합 선택;

 

일단 첫번째 값은 때려죽어도 해당 값이 답이기 때문에 dp[0] = arr[0] 으로 해주었고, i=1부터 n까지 for문을 돌리며 dp배열에 dp[i-1]+arr[i] , arr[i] 이 두값을 비교하여 큰값을 넣었다.

 

손으로 조금만 끄적이면 쉽게 알수있는 문제였다.