연속합

📍 문제 설명

 

💡 접근

dp[n]을 n번 인덱스를 마지막 항으로 하는 최대합으로 한다.

이전 항의 최대합 + 현재항, 현재항 중에서 큰 값을 넣는다.

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, answer;
    static int[][] board;
    static int[] arr, dp;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = kb.nextInt();
        arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        //dp[n]은 n번 인덱스를 마지막 항으로 하는 최대 합
        //여기서는 떨어져있으면 안되고 연속된 숫자여야한다.
        dp = new int[n];
        dp[0] = arr[0];
        answer = arr[0];

        for(int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
            answer = Math.max(answer, dp[i]);
        }
        System.out.println(answer);
    }

    private void solution() {
    }

}