연속합 2

연속합 1과 비슷한 문제다.

이 문제는 수 1개를 제외할 수도 있다. 무언가를 선택했을 때, 안했을 때 등은 DP의 전형적인 문제라고 할 수 있다.

우선 가장 기본적인 방법, 즉 연속합 1의 방법대로 문제를 푼다. 이 경우가 숫자를 모두 포함했을 때의 최댓값일 것이다.

그리고 n을 제외한 경우의 연속합의 최댓값은

• n-1까지의 연속합 최댓값 그대로
• n-1을 제외한 연속합의 최댓값 + 현재값

이렇게 두 가지 경우로 나뉜다. 이를 코드로 그대로 구현하면 된다.

답

package main

import (
	"bufio"
	"fmt"
	"math"
	"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()

	num := scanInt()
  
    // 모든 수를 더하는 경우 연속합을 저장
	allSum := num
  
    // 하나의 수를 제거했을 때의 연속합을 저장
	exceptOneSum := 0
	ans := math.MinInt64

	for ai := 1; ai < n; ai++ {
		num = scanInt()

        // 얘를 먼저 계산해야 한다.
        // allSum을 먼저 계산하면 n-1의 allSum이 아닌 n의 allSum으로 계산되기 때문
		exceptOneSum = max(allSum, exceptOneSum+num)
		allSum = max(allSum+num, num)

		ans = max(ans, max(allSum, exceptOneSum))
	}

	fmt.Println(ans)
}

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

일반적인 배열 유지

dp배열을 유지해서 문제를 해결해보면, 바로 이전값만 필요하므로 굳이 배열을 유지 할 필요 없이 변수로 유지해서 풀 수 있다는 것을 알 수 있다.

즉, 원래는 아래의 코드인데 위의 코드처럼 바뀐 것이다.

package main

import (
	"bufio"
	"fmt"
	"math"
	"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
}

var (
	dp [100001][2]int
)

func main() {
	n := scanInt()

	num := scanInt()
  
    // 모든 수를 포함한 연속합을 저장
	dp[0][0] = num
  
    // n을 제외하고 연속합을 저장
	dp[0][1] = 0
	ans := math.MinInt64

	for ai := 1; ai < n; ai++ {
		num = scanInt()

		dp[ai][0] = max(dp[ai-1][0]+num, num)
		dp[ai][1] = max(dp[ai-1][0], dp[ai-1][1]+num)

		ans = max(ans, max(dp[ai][0], dp[ai][1]))
	}

	fmt.Println(ans)
}

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