[algo] 부분 연속 수열의 최대합 구하기

문제 설명 

s[0], s[1] ... s[n] 의 수열이 있다.

이 중 부분 연속 수열의 합의 최대값을 구하는 문제는

sum( s[1], s[2], s[3]) 와 sum( s[3], s[4] ) 등 연속하는 부분 수열의 합의 최대값을 구하는

문제이다.

가장 직관적인 문제 해결법은 for 문을 중첩해서 둬서

0~1, 0~2, 0~3... 0~n
1~2, 1~3, 1~4,... 1~n
2~3, 2~4, 2~5,... 2~n
...

등 모든 가능한 연속 부분 수열의 합을 다 더해가면서 그 중 최대값을 구하는 것이다.

그런 무식한 방법은 조금만 수열의 개수가 많아져도 감당을 하지 못하게 된다.

문제 해결 

m'(n) 을 s[n] 을 포함하는 연속 수열의 합의 최대값이라고 하자.

m'(n) = max ( m'(n-1) , m'(n-1) + s[n])

이 된다. 이 말인즉, s[n-1]을 포함하는 연속 수열의 최대값에 s[n]을 더한 것과 그냥 s[n]
중 큰 값이 s[n]을 포함하는 최대 부분 수열의 합이 된다.

m(n) 을 s[0]~s[n]까지의 부분 수열의 합중 최대값. 즉 우리가 구하려고 하는 원래 문제이다.

이것은 m(n) = max( m(n-1), m'(n)) 이 된다.

이 말인즉, s[n]을 포함하는 최대부분수열의 합과, s[n]을 포함하지 않는 최대부분수열의 합 중

더 큰 것을 의미한다.

다시 한번 식을 정리하자면

m(n) = max ( m(n-1), m'(n)) = max(m(n-1), max( m'(n-1), m'(n-1) +  s[n])

이 된다.

덤으로, m(0) = s[0], m'(0) = s[0] 이다.

위 식의 내용을 코드로 구현하면 recursive 하게 문제를 해결하는 코드를 구할 수가 있다.

코드 구현

public class Problem {
    List<Integer> s;

    public Problem() { s = new ArrayList<Integer>(); }
    public void add(Integer a) {   s.add(a);   }
    
    public int solve() {
             return m(s.size());
    }

    public int m(int n) {
            if (n == 0) return s.get(0:
            else Math.max(m(n-1), m2(n));

    }

    public int m2(int n) {
           if (n == 0) return s.get(0);
           else Math.max(m2(n-1), m2(n-1) + s.get(n);
    }
}

위와 같이 풀면 되긴 하는데, 개선해야 될 점은 동적 프로그래밍 적용과

리컬시브가 아닌 방식으로 푸는 것이다.