/*
1. 문제 이해

[-2,1,-3,4,-1,2,1,-5,4]
* 정답부분 참고
각 인덱스를 시작점으로 잡고 모든 부분에 대한 부분 배열의 합을 구한다
이전에 계산했던 내용을 저장해서 사용한다
-> 이렇게 계산해도 Time Limit Exceeded 발생하네 ..

결국엔 이렇게 해도 n^2 시간이 발생하므로 시간초과
포인트는 n^2 가 걸리는 시간을 어떻게 nlogn이나 n으로 줄일 수 있는지임

* 정답 부분 참고
누적합이 음수라면 시작 인덱스를 다음으로 과감하게 옮긴다


이 문제는 직관적으로 문제를 바라보는것이 중요했다.
아마도 이렇게 접근하는건 어떨까 ?
나는 최대합을 구하고싶었다. 부분 배열로!
부분배열이라는 것은 연속된다는 것이 특징이다.

즉, 연속되어야 하므로 이전의 합들이 만약 음수라면 ? 이 부분들은 필요가 없어지므로 과감히 버릴 수 있다는 것을 아는 것이 포인트였다.

버린다는 것의 의미는 ? -> 현재 인덱스의 값과 이전 전체의 값들의 합을 비교해서 현재 인덱스부터 다시 출발한다는 것이다. 그러므로 비교해서 더 큰값을 total로 가져가는 것이다.

만약 이걸 처음부터 알았다면 그리고 기존에 작성한 n^2 를 소요하면서 모든 합을 구하려 했을때 비효율적인것을 직감했다면 다른 방법으로 접근할 수 있었어야 했다.

그리고 처음 total, maxTotal을 첫번째 인덱스로 지정해줬기 때문에 i 인덱스는 1부터 시작해야한다


*/

import java.util.*;

class Solution {
    public int maxSubArray(int[] nums) {
        int total = nums[0];
        int maxTotal = nums[0];


        for (int i=1; i<nums.length; i++) {
            total = Math.max(nums[i], total + nums[i]);
            maxTotal = Math.max(total, maxTotal);
        }

        return maxTotal;

        // for (int i=0; i<nums.length; i++) {
        //     int total = 0;
        //     for (int j=i; j<nums.length; j++) {
        //         total += nums[j];
        //         max = Math.max(total, max);
        //         if (total < 0) {
        //             break;
        //         }
        //     }
        // }

        // return max;
    }

    private int sum(int[] arr, int start, int end) {
        int cnt = 0;
        for (int i=start; i<end + 1; i++) {
            cnt += arr[i];
        }
        return cnt;
    }
}