DP - 가장 긴 증가하는 부분 수열1,2 / 연속합/ 가장 큰 정사각형

11053 가장 긴 증가하는 부분 수열

d = [0 for i in range(1002)]

n = int(input())
a = list(map(int, input().split()))
d[0] = 1

for i in range(1, n):
    d[i] = 1
    for j in range(0, i):
        if a[j] < a[i]:
            d[i] = max(d[i], d[j] + 1)

print(max(d))

O(n^2)

#include <bits/stdc++.h>
using namespace std;
int d[1001];
int num[1001];

int main(void){
    int n = 0, mx = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> num[i];
    
    for (int i = 0; i <n ;i++)
        d[i] = 1;
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (num[i] > num[j])
                d[i] = max(d[i], d[j] + 1);
        }
    }
    cout << *max_element(d, d+n);
}

12015 가장 긴 증가하는 부분 수열 2

#include <bits/stdc++.h>
using namespace std;


int main(void){
    int n = 0;
    cin >> n;
    vector<int> v;
    
    for (int i = 0; i < n ; i++)
    {
        int num = 0;
        cin >> num;
        auto it = lower_bound(v.begin(), v.end(), num);
        if (it != v.end())
            *it = num;
        else
            v.push_back(num);
    }
    cout << v.size();
}

이진탐색, O(nlogN)

1912 연속합

n = int(input())
arr = list(map(int, input().split()))
dp = [0] * n
dp[0] = arr[0]

for i in range(1, len(dp)):
    if dp[i-1] + arr[i] > arr[i]:
        dp[i] = dp[i-1] + arr[i]
    else:
        dp[i] = arr[i]
mx = max(dp)
print(mx)

---

#include <bits/stdc++.h>
using namespace std;

long long num[100001];
long long d[100001];

int main(void){
    int n = 0;
    cin >> n;
    
    for (int i = 0; i<n ; i++)
        cin >> num[i];
    d[0] = num[0];
    for (int i = 1; i < n; i++)
    {
        if (d[i-1] + num[i] > num[i])
            d[i] = d[i-1] + num[i];
        else
            d[i] = num[i];
    }
    
    cout << *max_element(d, d+n);
}

1915 가장 큰 정사각형

n, m = map(int, input().split())
board = [list(map(int, input())) for _ in range(n)] # 배열 입력받음
dp = [[0] * m for _ in range(n)]  # 정사각형의 한변 길이 저장

for i in range(n):
    dp[i][0] = board[i][0]
    
for j in range(m):
    dp[0][j] = board[0][j]
    
for i in range(1, n):
    for j in range(1, m):
        cur = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1])
        if board[i][j] != 0:
            dp[i][j] = cur + board[i][j]
	# board[i][j] == 0 이면 dp[i][j]는 그대로 0

mx = max(map(max, dp)) # 2차원 리스트에서 최대값 구하기
print(mx * mx)