부분 배열의 합이 0에 가까운 값을 찾는 방법

• 
  

  i	0	1	2	3	4	5	6	7	8	9
  a[j]	-14	7	2	3	-8	4	-6	8	9	11

• 0에 가장 가까운 절대값을 찾는 것 
• 2 3 -8 4 또는 3 -8 4 또는 3 -8 4 -6 8 일 때
• 
  
• 최고로 무식하게 찾는 다면 다 돌면서 모두 차으면 되는것 O(NxN).
• 부분합 [i] ~ A[j]의 구간의 합을 momoization 방법으로 미리 저장 

• 이 값이 0에 가깝다는 말은 psum[]의 두 값의 차이가 가장 적다는 뜻이다.
• 주어진 배열에서 가장 가까운 두 값을 찾기 위한 간단한 방법은 이 배열을 정렬한 뒤 인접한 원소들을 확인하는 것이다.
• 정렬은 O(NlgN)시간에 수행할 수 있다.
• i-j의 구간 합 계산은 O(NlgN)시간에 수행할 수 있다.
• 부분합을 구하는 것과 인접한 원소들을 확인하는 것 모두 O(N)에 할 수 있으니 이 알고리즘 수행시간은 O(NlgN) 

void solve(const vector <int> &A)

{

int N = A.size();

int sum[100] = { 0, }; //0 -> + , 1 -> minus value 

int dp[100];

int answer = 9999;

vector <int> ::const_iterator it;

int k = 1;

int aa, bb;

for (it = A.begin(); it != A.end(); ++it)

{

sum[k] = sum[k - 1] + *it;

k++;

}

sort(sum+1, sum+N +1);

for (int k = 1; k <= N; k++)

{

answer = min(abs(sum[k] - sum[k - 1]), abs(answer));

}

cout << answer << endl;

}