13398

1. 경우를 적어보며 규칙, 점화식을 찾는다.
   

2. dp[i][0]은 중간에 제거 없는 경우
   dp[i][1]은 자신을 제거한 경우

• 첫번째 경우를 보면 자신에서 시작한경우와 전까지 더한경우 크기를 비교해서 큰 값을 넣으면 된다
  • Max(dp[i-1][0]+array[i], array[i])
• 두번째 경우 자신을 제거한 경우와 앞에 제거 되어 있어 자신을 제거하지 않은 경우 비교 한다
  • Max(dp[i-1][0], dp[i-1][1]+array[i])

import java.util.Scanner;

public class ContinueSum13398 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int array[] = new int[n];
        int dp[][] = new int[n][2];

        for(int i=0; i<n; i++){
            array[i] = sc.nextInt();
        }

        int max = array[0];
        dp[0][0] = array[0];
        dp[0][1] = array[0];

        for(int i =1; i<n; i++){
            dp[i][0] = Math.max(dp[i-1][0]+array[i], array[i]);
            dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]+array[i]);
            max = dp[i][0]와 dp[i][1]와 max 비교
        }
    }
}

import sys

n = int(input())
array = [0 for _ in range(n)]
array = list(map(int,sys.stdin.readline().split(" ")))
dp = [[0 for _ in range(2)]for _ in range(n)]

# 처음값 초기화
max_num = dp[0][0] = dp[0][1] = array[0]

for i in range(1,n):
    #제거하지 않는 경우
    dp[i][0] = max(dp[i-1][0]+array[i] , array[i])
    #print(dp[i][0])
    #제거한 경우
    dp[i][1] = max(dp[i-1][0], dp[i-1][1]+array[i])
    max_num = max(max(dp[i][0], dp[i][1]),max_num)
    
print(max_num)