부분합 (1차원 배열)

부분합 알고리즘은 누적합의 차를 통해 부분합을 구하는 방식으로 빠르게 부분합을 계산하는 알고리즘

 

 

배열을 하나 더 만들어서 index까지의 합을 돌린다음에 이 합을 구한 벡터를 이용하여 특정 범위의 부분합을 구할수있다.

#include <algorithm>

int solution(vector<int> &A) {
    vector<int> B (A.size(), 0);

    B[0] = A[0];
    int _max = B[0];
    for(int i=1; i<A.size(); i++)
    {
        B[i] = max( B[i-1] + A[i] , A[i] ); 
        // 기존 i-1까지 합 B[i-1] + A[i] 를 합친게 큰지
        // 아니면 A[i] 부터 새로 시작하는게 큰지 

        if (_max < B[i])
            _max = B[i];
    }
    return _max;
}

TimeComplex: O(n)

SpaceComplex: O(n)

 

 

Colidity - MaxSliceSum

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/

9. Maximum slice problem lesson - Learn to Code - Codility

 

 

 

index기준으로 합 나눌 때

ex) sum1 = A[0] + A[1] ... A[i-1],   sum2 = A[i] + A[i+1] .. A[A.size()-1]

마찬가지로 배열을 한번 순회하여 합을 구한다음에

start = 0, last = sum 으로 초기화하고 인덱스에맞춰 start에는 더하고 last에는 뺀다.

#include <algorithm>

int solution(vector<int> &A) {
    
    int sum = 0;
    for(int i=0; i<A.size(); i++)
        sum += A[i];
    
    int num = 0;
    int _min = 100000000; // 1,000 * 100,000

    for(int i=0; i<A.size()-1; i++)
    {
        num += A[i];
        sum -= A[i];

        int tmp = abs(num - sum);
        // cout << num << " " << sum << "  tmp: " << tmp <<endl;

        if (_min > tmp)
            _min = tmp; 
    }
    return _min;
}

 

Colidity - TapeEquilibrium

https://app.codility.com/programmers/lessons/3-time_complexity/

3. Time Complexity lesson - Learn to Code - Codility

 

 

또한 index에 따른 부분합의 최대값을 구할때는 다음과 같이 구할 수 있다.

sum_A[0] = A[0];
for(int i=1; i<A.size()-1; i++)
    sum_A[i] = max(sum_A[i-1] + A[i], A[i]);

(바로 앞 index 까지의 부분합 + 현재 index의 원소) 보다 (현재 index의 원소) 가 크면 굳이 앞의 부분합을 더하면 손해이므로 더해줄 필요가없다

 

 

 

#include <algorithm>

int solution(vector<int> &A) {

    vector<int> front_B(A.size(), 0);
    vector<int> back_B(A.size(), 0);

    front_B[0] = 0;
    for(int i=1; i<A.size()-1; i++)
        front_B[i] = max(0, front_B[i-1] + A[i]);
    // Math.max(0, value)처럼 0과 비교해 주는 이유는, X,Y가 인접한 경우와 Y,Z가 인접한 경우 값이 0이므로 값으로 넣을 수 있는 가장 작은 값  
    // ex) double slice (3, 4, 5)

    back_B[A.size()-1] = 0;
    for(int i=A.size()-2; i>0; i—)
        back_B[i] = max(0, back_B[i+1] + A[i]);

    int _max = -1000000000; // -10,000 * 100,000
    for(int i=1; i<A.size()-1; i++)
        _max = max(_max, front_B[i-1] + back_B[i+1]);
    
    return _max;
}

Colidity - MaxDoubleSliceSum

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/

9. Maximum slice problem lesson - Learn to Code - Codility