연속합

왜 이 문제를 푸는데 많이 헷갈렸을까...

우선 N <= 100,000 이므로, O(N^2)이 넘어가면 문제를 해결할 수 없다. 그렇다면 O(NlgN) 혹은 O(N) 등으로 해결하라는 소리가 된다.

연속합이 최댓값인 구간을 찾으려고 생각해보면, 양수는 무조건 더하는게 맞고 음수일 때 어떻게 해야 할지 고민을 해야 한다.

음수일 때, 이 값을 더하고 그 이후의 값이 계속 커지게 된다면 이 값을 사용하면 되고, 아니면 구간을 다시 시작하면 된다. 즉, 음수 이후의 상황에 대해 고민을 해야한다.

새로 구간을 다시 시작하는 경우는 어떤 경우일까? 조금 생각해보면, 지금까지의 합 + 현재값 보다 현재값이 크면 새로 시작하면 된다.

이 아이디어만 있으면 문제를 쉽게 해결할 수 있다.

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func init() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
}

func scanInt() int {
    sc.Scan()
    ret, _ := strconv.Atoi(sc.Text())
    return ret
}

func main() {
    n := scanInt()

    ans := scanInt()
    candi := ans
    for ni := 1; ni < n; ni++ {
        num := scanInt()
        // 이전 연속합+현재값 < 현재값이면
        // 이전 구간은 버리고 현재값부터 다시 시작한다.
        candi = max(candi+num, num)
        // 최댓값이 있는 구간의 값을 유지한다.
        ans = max(ans, candi)
    }

    fmt.Println(ans)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}