152. Maximum Product Subarray / LeetCode

루프를 3번 사용해서, 모든 부분집합의 곱을 구한 뒤에, 가장 큰 값을 찾는 방식으로 푸는 방법이 있습니다.
하지만 이방법으로는 time limit에 걸립니다.

• 길이가 1인 부분집합을 구하고
• 최대값을 구하고
• 길이가 1일 부분집합을 길이가 2인 부분집합으로 만들기 위해서, 길이가 1인 부분집합의 다음번 수를 곱합니다.
• 최대값을 구합니다.
• 3번 ~ 4번을 반복해서, nums와 같은 부분집합을 만들때 까지 반복합니다.

이렇게 구현하면, accpected는 되지만, 그렇게 속도가 빠른 방식은 아니네요.
곱하기만 하기 때문에, 0과 음수의 개수를 고려 해서, 구현하면 보다 빠른 방식찾을 수 있을 것 같습니다.

class Solution {
    public int maxProduct(int[] nums) {
        int r = nums[0];
        int[] v = new int[nums.length];
        int N = v.length;

        for(int i=0; i<v.length; ++i)
            v[i] = 1;

        for(int lengthOfSubarray = 1;
            lengthOfSubarray <= N;
            ++lengthOfSubarray) {

            for(int i=lengthOfSubarray-1, vi=0;
                i<N;
                ++i, ++vi) {
                v[vi] *= nums[i];
                r = Math.max(r, v[vi]);
            }
        }

        return r;
    }
}