문제 설명
특정 숫자 배열이 주어졌을때, 합이 최대가 되는 부분배열을 찾는 것!
나의 방법
1. 브루트포스(Time out)
배열에 각각 접근해서 부분 배열의 값을 더한 후에 최대 값을 찾는 방법
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max = -100000;
for(int i = 0; i < nums.size(); i++){
int sum = 0;
for(int j = i; j < nums.size() ; j++){
sum += nums[j];
if(max < sum){
max = sum;
}
}
}
return max;
}
};한계점
이중 for문의 사용으로 O(N^2)의 시간 복잡도를 갖게 됨.
2. 직전 값이 음수면 더하지 않는다!
더하기 직전 값이 음수라면, 더한 이후의 값은 직전의 수보다 "무조건" 작음을 이용!
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max = -100000;
int idx = 0;
int sum = 0;
for(int i =0 ; i < nums.size(); i++){
sum += nums[i];
if(max < sum){
max = sum;
}
if(sum < 0){
sum = 0;
i = (++idx) - 1;
}
}
return max;
}
};알고리즘 설명
sum의 값이 0으로 초기화되는 경우 : sum 값이 음수일 때!
sum의 값이 갱신되는 경우 : sum의 값이 양수일 때sum과 max값의 비교가 sum의 부호 판별 이전에 일어나는 이유
가령 nums = [-1,-2,-3,-4]와 같은 음수로만 이루어진 배열이 존재한다고 가정하자.
sum의 부호판별을 먼저하게 된다면 sum의 값은 항상 0이 될 것이고, 그 다음 최대값 판별을 진행하여 최종적으로 0이라는 값만 남게될 것이다.
위와 같은 문제점을 해결하기 위해 순서를 달리하여, 음수더라도 값 자체가 최대 값 인가를 먼저 비교한 이후 sum의 값을 갱신하는 과정으로 알고리즘을 구성한 것이다.
변수 설명
idx: "Sub Array"의 index가 저장되는 변수
sum: "Sub Array"의 합이 저장되는 변수
개선점
공간복잡도적으로는 그래도 준수한 성능을 보였으나 여전히 시간복잡도 측면에서 부족한 부분이 존재하였다.
해당 문제를 "분할 정복", "DP"의 방법으로 풀수도 있다고 하는데, 알고리즘 공부를 더 한 이후에 새로운 접근법으로 해당 문제를 풀어보고 싶다.
