Maximum Subarray: Dynamic Programming**

First Thoughts: going forward, seeing if the new value will add on to making the maximum value (새로 들어올 값들이 과연 도움이 될 지, 해가 될 지 판단하려고 했다). 문제점-> 너무 범위가 크다. 이를 정확히 판단하려면 이 다음에 오는 모든 값들의 조합을 봐야한다. 따라서 nested for-loop을 써서 일일이 확인하게 되어, 결국 O(N2) solution이 된다.

My Solution O(N2)

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        for (int i=0; i<nums.length; i++) {
            int sum = nums[i];
            if (sum>max) max =sum;
            for (int j=i+1; j<nums.length; j++) {
                sum+=nums[j];
                if (sum>max) max=sum;
            }
        }
        return max;
    }
    
}

Improved Solution O(N): 앞으로 예상하지 말고, 이미 가진 값을 버릴지, keep할지 판단 -> look backwards

int max = nums[0];
int current = nums[0];
for (int i=1; i<nums.length; i++) {
	int current = current>0 ? current+nums[i] : nums[i];
    if (current>max) max = current;
}
return max;

Catch Point

1. Instead of forward evaluation (앞으로 이 값을 더하는게 과연 도움이 될지..안될지 어렵게 판단하는 것보다는) backward evaluation (그동안 값들은 한 숫자로 명확한 값이 있으니, 이 값이 양수라면 분명 도움이 될거고, 아니라면 버리기). 이렇게 앞으로 가면서 누적 합이 음수라면 과감히 버리고, 양수라면 받고, 이 경우에는 또 기존의 최댓값보다 큰 지 체크해야 된다.

2. Best time to buy and sell stock 과는 대칭적인 사고?를 가지고 있는거 같다. 그때는 하나씩 iterate 하면서 이 값이 어떤 의미를 가지는지 보았다면 (기존의 값보다 작다면 최솟값의 가능성, 크다면 이윤을 늘릴 수 있는 가능성), 이번 케이스는 기존의 값이 최댓값을 만드는데에 도움을 줄 수 있는지 (음수면 갉아먹는 것 뿐..)

3. 값을 반환하는 것이기 때문에 keep track하기 더 쉬운 경향이 있다. 기존의 작업들은 모두 숫자 하나로 reduce 가능하기 때문. 심지어 이게 양수인지 음수인지 판별해서 더하거나 버리거나 둘 중 하나만 하면 된다.