// [참고]

// 카데인 알고리즘: 이전요소의 부분합을 알면 현재요소의 최대값을 알 수 있다.

// 양수만이라면 단순히 dp로 dp[nums.length-1] 값이나 total이라는 계산값을 리턴하겠지만,

// 음수가 포함되었으므로 bestSum과 currentSum을 별개의 변수로 처리한다.

// currentSum은 최대 sum을 구해야 하므로 음수값일때 강제로 0으로 업데이트 후 계산을 실행한다.

// https://velog.io/@wind1992/Leetcode-53.-Maximum-Subarray

//

// [풀이방식]

// 1. 카데인 알고리즘 2. DP

// [성능]

// dp 배열보다 변수를 사용하는 것이 공간 복잡도를 줄일 수 있다. 또한 for문 1개로 해결 가능하다.

class Solution {

public int maxSubArray(int[] nums) {

int bestSum = nums[0];

int currentSum = 0;

for (int n : nums) {

if (currentSum < 0) { // 1. 업데이트

currentSum = 0;

}

// 2. 계산

currentSum += n;

bestSum = Math.max(currentSum, bestSum);

}

return bestSum;

}

public int maxSubArrayDp(int[] nums) {

int n = nums.length;

int[] dp = new int[n];

dp[0] = nums[0];

int maxSum = dp[0];

for (int i = 1; i < n; i++) {

dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);

maxSum = Math.max(maxSum, dp[i]);

}

return maxSum;

}

}