Maximum Subarray //10211

• 문제
  크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다.
  여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하자. 즉, max1 ≤ i ≤ j ≤ N (X[i]+...+X[j])를 구하자.
  
  // 시간 제한: 1초, 메모리 제한: 256MB

• 입력
  입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.
  각 테스트케이스 별로 첫 번째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000)
  그리고 두 번째 줄에 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다.

• 출력
  각 테스트케이스 별로 maximum subarray의 합을 줄로 구분하여 출력한다.

// Created by dongwan-kim on 2022/08/13.
#include<iostream>
#include<algorithm>

using namespace std;

int t, n, dp[1000], num;

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> num;
            sum += num;
            sum = max(sum, num);
            dp[i] = sum;
        }

        sort(dp, dp + n);
        cout << dp[n - 1] << "\n";
    }
}

풀이

dp 알고리즘을 활용하여 문제를 해결했다.

로직은 정수를 받을 때마다 바로 처리해주었는데,
sum 변수를 만들어서 숫자가 들어올때마다 더해주고 sum은 새로 들어온 숫자와 자기 자신 중 더 큰값을 대입해 주었다.
이 후 그 수를 dp배열에 삽입했다.

sort로 오름차순 정렬 후 마지막 index를 출력해주어서 최댓값, 즉 정답을 출력해 주었다.