█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 2170

Problema 0x94 - Subarreglo de máxima suma

  • Autor: Javier
  • Fecha: 2020-11-27 03:21:16 UTC (Hace alrededor de 2 años)
Caso # Resultado Tiempo Memoria
#1
Incorrecto
0.005 s 1 KBi
#2
Correcto
0.005 s 1 KBi
#3
Correcto
0.006 s 1 KBi
#4
Incorrecto
0.007 s 1 KBi
#5
Incorrecto
0.006 s 1 KBi
#6
Correcto
0.006 s 1 KBi
#7
Correcto
0.006 s 1 KBi
#8
Correcto
0.006 s 1 KBi
#9
Correcto
0.007 s 1 KBi
#10
Correcto
0.007 s 1 KBi
#11
Correcto
0.008 s 1 KBi
#12
Correcto
0.005 s 1 KBi
#13
Incorrecto
0.006 s 1 KBi
#14
Correcto
0.006 s 1 KBi
#15
Incorrecto
0.006 s 1 KBi
#16
Incorrecto
0.006 s 1 KBi
#17
Incorrecto
0.052 s 1 KBi
#18
Incorrecto
0.053 s 1 KBi
#19
Incorrecto
0.055 s 2 KBi
#20
Incorrecto
0.054 s 1 KBi
#21
Incorrecto
0.038 s 1 KBi
#22
Incorrecto
0.056 s 1 KBi
#23
Incorrecto
0.031 s 2 KBi
#24
Incorrecto
0.032 s 2 KBi
Puntos totales: 42 / 100

Código

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int max_across(int a[], int left, int mid, int right) {
    int sum = 0;
    int left_result = INT_MIN;
    for (int i = left; i <= mid; i++)
    {
        sum = sum + a[i];
        if (sum > left_result) {
            left_result = sum;
        }
    }
    sum = 0;
    int right_result = INT_MIN;
    for (int i = mid+1; i <= right; i++)
    {
        sum = sum + a[i];
        if (sum > right_result) {
            right_result = sum;
        }
    }
    int max1 = max(left_result, left_result + right_result);
    return max(max1, right_result);
}

int solve(int a[], int left, int right) {
    if(left == right) {
        return a[left];
    }
    int midPoint = (right + left)/2;
    int max_left = solve(a, left, midPoint);
    int max_right = solve(a, midPoint + 1, right);
    int max_crossing = max_across(a, left, midPoint, right);
    int max_border = max(max_left, max_right);
    return max(max_border, max_crossing);
}

int main()
{
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int best = solve(a, 0, n-1);
    cout << best << endl;
    return 0;
}