CodeForce - Just Eat It!(1285B)

문제(링크)

문제 설명:
배열의 총 합보다 자기 자신이 아닌 연속된 부분 배열의 합이 총 합보다 크거나 같으면 "NO", 아니라면 "YES"를 출력합니다.

풀이:
왼쪽과 오른쪽에서 부터 각각 prefix sum을 구하여 0보다 작거나 같아질 때가 "NO" 입니다.
prefix sum이 0이하가 된다는 의미는 그 감소하는 구간이 없었다면 기존의 총합이 더 커질 수 있었다는 의미입니다.
따라서 감소하는 구간을 제외한 부분 배열이 총합보다 커지는 구간이 반드시 존재합니다.

#include<iostream>
#include<string>
#include<algorithm>
#include<math .h="">
#include<vector>
#include<queue>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pii pair<int int="">

int T, N;
long long arr[100000];

int main(void) {
 FIO;

 cin &gt;&gt; T;

 while (T--) {
  cin &gt;&gt; N;

  long long sum = 0;

  for (int i = 0; i &lt; N; i++)
  {
   cin &gt;&gt; arr[i];
   sum += arr[i];
  }

  long long leftSum = 0;
  long long rightSum = 0;
  bool flag = false;

  for (int i = 0; i &lt; N; i++)
  {
   leftSum += arr[i];
   rightSum += arr[N - i - 1];

   if (leftSum &lt;= 0 || rightSum &lt;= 0) {
    flag = true;
    break;
   }
  }
  if (flag)
   cout &lt;&lt; "NO\n";
  else
   cout &lt;&lt; "YES\n";
 }
}