JOI 一次予選 2021 (第 2 回) C - 分割 (7Q, 難易度 2)

for 文の練習！

• 問題へのリンク

問題概要

長さ の数列 (すべての要素は互いに相異なる) について、最大値を考えたとき、その左側の総和と、右側の総和をそれぞれ求めよ。

制約

• 

解法

この問題では、数列 の最大値だけではな、 が最大となるような も求める必要がある。

それが求められれば、その左側と右側の総和を求めれば良い。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    int max_value = 0;  // 最大値
    int max_index = -1;  // 最大となる i
    for (int i = 0; i < N; ++i) {
        if (A[i] > max_value) {
            max_value = A[i];
            max_index = i;
        }
    }
    
    // max_index の左側の総和 left と右側の総和 right を求める
    int left = 0, right = 0;
    for (int i = 0; i < max_index; ++i) left += A[i];
    for (int i = max_index + 1; i < N; ++i) right += A[i];
    
    // 出力
    cout << left << endl;
    cout << right << endl;
}