Untitled

#include <iostream>
#include <ctime>
using namespace std;
int cach_1(int a[], int n)
{
    int max = a[0];
    for (int i = 0; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            int tong = 0;
            for (int k = i; k <= j; k++)
            {
                tong += a[k];
                if (tong > max)
                {
                    max = tong;
                }
            }
        }
    }
    return max;
}
int cach_2(int a[], int n)
{
    int max = a[0];
    for (int i = 0; i <= n; i++)
    {
        int tong = 0;
        for (int j = i; j <= n; j++)
        {

            tong += a[j];
            if (tong > max)
            {
                max = tong;
            }
        }
    }
    return max;
}
int max_left(int start, int end, int a[])
{
    int max = a[end], sum = 0;
    for (int i = end; i >= start; i--)
    {
        sum += a[i];
        if (sum > max)
        {
            max = sum;
        }
    }

    return max;
}
int max_right(int start, int end, int a[])
{
    int max = a[start], sum = 0;
    for (int i = start; i <= end; i++)
    {
        sum += a[i];
        if (sum > max)
        {
            max = sum;
        }
    }

    return max;
}
int cach_3(int start, int end, int a[])
{
    int sum;
    if (a[start] == a[end])
    {
        return a[start];
    }
    int mid = (start + end) / 2;
    int left = cach_3(start, mid, a);
    int right = cach_3(mid + 1, end, a);
    int t_mid = max_left(start, mid, a) + max_right(mid + 1, end, a);
    return max(t_mid, max(left, right));
}
int cach_4(int a[], int n)
{
    int w = a[0], maxSum = a[0];
    for (int i = 0; i <= n; i++)
    {
        w = max(a[i], w + a[i]);
        if (w > maxSum)
        {
            maxSum = w;
        }
    }
    return maxSum;
}
int main()
{
    int n = 300;
    int dayso[n];
    for (int i = 0; i <= n; i++)
    {
        dayso[i] = rand() % 100 - 50;
        cout << dayso[i]<< " " ;
    }
    cout<<endl;
    clock_t begin = clock();
    cout << cach_1(dayso, n) << endl;
    clock_t end = clock();
    cout << "thoi gian chay\t" << end - begin << endl;
    begin = clock();
    cout << cach_2(dayso, n) << endl;
    end = clock();
    cout << "thoi gian chay\t" << end - begin << endl;
    begin = clock();
    cout << cach_3(0, n, dayso) << endl;
    end = clock();
    cout << "thoi gian chay\t" << end - begin << endl;
    begin = clock();
    cout << cach_4(dayso, n) << endl;
    end = clock();
    cout << "thoi gian chay\t" << end - begin << endl;
    return 0;
}