flynn.go

/*
풀이 1
- 아래와 같은 memo 배열을 만들어서 풀이할 수 있습니다 (참고: Kadane's Algorithm)
  memo[i] = nums[:i] 중에서 nums[i]를 반드시 포함하는 부분 배열의 최대 합

Big O
- N: 주어진 배열 nums의 길이
- Time complexity: O(N)
- Space complexity: O(N)
*/

func maxSubArray(nums []int) int {
	n := len(nums)

	memo := make([]int, n)
	copy(memo, nums)

	maxSum := nums[0]

	for i := 1; i < n; i++ {
		if memo[i-1] > 0 {
			memo[i] += memo[i-1]
		}

		if maxSum < memo[i] {
			maxSum = memo[i]
		}
	}

	return maxSum
}

/*
풀이 2
- 알고리즘의 전개 과정을 보면 O(N)의 공간복잡도를 갖는 memo가 필요하지 않다는 걸 알 수 있습니다
- memo 배열 대신 현재 계산 중인 부분 배열의 합만 계속 갱신합니다

Big O
- N: 주어진 배열 nums의 길이
- Time complexity: O(N)
- Space complexity: O(1)
*/

func maxSubArray(nums []int) int {
    maxSum, currSum := nums[0], nums[0]

    for i := 1; i < len(nums); i++ {
        if currSum > 0 {
            currSum += nums[i]
        } else {
            currSum = nums[i]
        }
        
        if maxSum < currSum {
            maxSum = currSum
        }
    }

    return maxSum
}