Покупка Конфет Задача c++ [закрыт]

#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream inp;
ofstream otp;
inp.open("input.txt");
otp.open("output.txt");
int a[101], ans[4], n = 0, max1 = 0, max1n[5], max2 = 0, max2n[5], x = 0;
inp >> n;
for (int i = 0; i < n; i++) {
    inp >> a[i];
}
for (int i = 0; i < n - 1; i++) {
    x = a[i] + a[i + 1];
    if (x > max1) {
        max1 = x;
        max1n[0] = i;
        max1n[1] = i + 1;
    }
    else {
        continue;
    }
}
for (int i = 0; i < n - 1; i++) {
    x = a[i] + a[i + 1];
    if (x > max2) {
        if (i != max1n[0] && i + 1 != max1n[0] && i != max1n[1] && i + 1  != max1n[1]) {
            max2 = x;
            max2n[0] = i;
            max2n[1] = i + 1;
        }
        else {
            continue;
        }
    }
    else {
        continue;
    }
}
otp << max1n[0] + 1 << " " << max1n[1] + 1 << " " << max2n[0] + 1 << " " << max2n[1] + 1;

return 1;

Решение за чистый O(n). Упражнение - переписать используя только константую память (не читать массив целиком).

int main() {
    int n, a[100], mPrex, mRes, res[3];
    cin >> n;
    for (int i=0;i < n;i++)
        cin >> a[i];
    res[0] = 1;
    res[1] = 1;
    res[2] = 3;
    mPrex = a[0] + a[1];
    mRes = mPrex + a[2] + a[3];
    for (int i=3; i < n-1;i++){
        if (a[i-2] + a[i-1] > mPrex){
            mPrex = a[i-2] + a[i-1];
            res[0] = i-1;
        }
        if (mPrex + a[i] + a[i+1] > mRes){
            mRes = mPrex + a[i] + a[i+1];
            res[1] = res[0];
            res[2] = i+1;
        }
    }
    cout << res[1]<<" "<<res[1] + 1 << " "<<res[2]<<" "<<res[2] + 1;
    return 0;
}

В чём собственно задумка. Мы можем легко поддерживать где в массиве был максимум до какой-то позиции. Поэтому мы перебираем правую пару, а левая пара - максимум из всего что было до правой. Правая пара начинается с позиции i в цикле что от 3. Дальше вроде бы всё понятно.

a[]-массив количества конфет
n-длина массива

for (int i = 0; i < n-1; i++)
    a[i]=a[i]+a[i+1];
n--;
int x;
for (int i = 0; i < n-1; i++)
    for (int j = i+2; j < n; j++){
        if(j-i>1){
            x=a[i]+a[j];
            //cout <<"i="<<i<<";\tj="<<j<<";\tx="<<x<<";\tmax="<<max<<endl;//для отладки
            if (max<x){
                max=x;
                res[0]=i;
                res[1]=j;
            }
        }
    }
for (auto x : res)
     cout << x+1<<" "<< x+2<<" ";
return 0;

https://ideone.com/n8W7Zh

решение за O(n)

for (int i = 0; i < n - 1; i++) {
    x = a[i] + a[i + 1];
    if (x > max1) {
        max1 = x;
        max1n[0] = i;
        max1n[1] = i + 1;
    }
}
for (int i = 0; i < n - 1; i++) {
    x = a[i] + a[i + 1];
    if (i != max1n[0] && i + 1 != max1n[0] && i != max1n[1] && i + 1  != max1n[1]) {
        if (x > max2) {
            max2 = x;
            max2n[0] = i;
            max2n[1] = i + 1;
        }
    }
    else {//если числа пересекаются
        if(i+1 == max1n[0] && i+3<n){
            x = a[i] + a[i+1] + a[i+2] + a[i+3];//смотрю сумму после сдвига
            if (x>max1+max2){//если она мне нравится
                max1n[0] = i;//записываю как текущий результат
                max1n[1] = i+1;
                max2n[0] = i+2;
                max2n[1] = i+3;
            }
        }
    }
}
    cout << max1n[0] + 1 << " " << max1n[1] + 1 << " " << max2n[0] + 1 << " " << max2n[1] + 1;

return 0;

https://ideone.com/Z5U0sG