[알고리즘문제] 릿코드 Maximum Subarray(시간초과, dfs)

https://leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

정수 배열이 주어지면 배열내 인접 원소의 합중 가장 큰 합을 return 시키라는 문제이다

ex1) [-2,1,-3,4,-1,2,1,-5,4] 배열이 있다면 인접 원소중 4, -1, 2, 1을 합한 6이 가장 큰 숫자이다.

ex2) [1] 배열에서는 1이 원소의 합 중 가장 큰 숫자이다.

ex3) [5, 4, -1, 7, 8] 배열에서는 5, 4, -1, 7, 8을 합한 23이 가장 큰 숫자이다.

impl Solution {
    pub fn max_sub_array(mut nums: Vec<i32>) -> i32 {
        if nums.len() == 1 { return nums[0]; }
        else if nums.len() == 0 { return 0; }
        let mut max = nums[0];
        for i in 0..nums.len(){
            Solution::dfs(&mut nums, i, 1, &mut max);
        }
        max
    }

    fn dfs(nums: &mut Vec<i32>, pos: usize, mut cnt : usize, max: &mut i32){
        if cnt > nums.len(){ return; }

        let mut tmp = nums[pos];
        for i in pos+1..cnt {
            tmp += nums[i];
        }

        if tmp > *max { *max = tmp; }

        cnt += 1;
        Solution::dfs(nums, pos, cnt, max);
    }
}

DP 카테고리 이지만 일단 dfs로 풀어보았다.

dfs 함수에 인자로 nums 배열, 현재 가리키고 있는 원소의 위치값 pos, pos부터 cnt번째 까지의 합을 계산할 cnt, 합 중 최대값을 저장할 max

위의 코드로 계산하면 시간 초과가 발생한다.

계산할 수 있는 모든 경우의 수를 계산하므로 nums의 원소가 많아질 수록 효율이 떨어지는 코드이다.

time complexity : O(n^2)

space complexity : O(n)

Dynamic Programming 풀이방법을 공부한 후 다시 풀어봐야겠다.