[LeetCode] 자바 53. Maximum Subarray

문제는 '들어온 배열의 Sub배열의 합이 가장 큰 경우의 수의 합을 구해라' 입니다.

---

해결 방안으로는 divide & conquer로 하면 좋겠다 라고 하는데, 네 생각이 안납니다. 그래서 일단 풀어보겠습니다.

첫번째.

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

아이디어는 '이중 for문을 돌면서, 가장 큰 조합을 계속 찾아가는 것입니다.'

통과는 했는데 보시다시피 런타임이 쓰레기네요. 좀더 고민을 해봐야 겠습니다. 분할정복으로 푸는 방법을요..

두번째.

고민중....