// 1 số mẫu test: => random 1 mảng 1 chiều có số lượng phần tử từ ít tới nhiều
// 10 phần tử, 100 phần tử, 1,000, 10,000, 100,000 phần tử

#include <iostream>
#include <stdlib.h>     /* srand, rand */
#include <time.h>
using namespace std;
double ThuatToan1(int a[], int n,double time_use) {
    int maxSum = 0;
    clock_t start, end;
    for (int i = 0; i < n; i++)
    {
        start = clock();
        for (int j = i; j < n; j++)
        {
            int thisSum = 0;
            for (int k = i; k <= j; k++)
                thisSum += a[k];
            if (thisSum > maxSum)
                maxSum = thisSum;
        }
        end = clock();
        double time = (double)(end - start) / CLOCKS_PER_SEC;
        time_use += time;
        if (time_use > 30)
            return -1;
    }

    cout << maxSum << endl;
    return time_use;
}

double ThuatToan2(int a[],int n,double time_use)
{
    int maxSum = 0, thisSum = 0;
    clock_t start, end;

    for (int j = 0; j < n; j++)
    {
        start = clock();
        thisSum += a[j];
        if (thisSum > maxSum)
            maxSum = thisSum;
        else if (thisSum < 0)
            thisSum = 0;
        end = clock();
        double time = (double)(end - start) / CLOCKS_PER_SEC;
        time_use += time;
        if (time_use > 30)
            return -1;
    }

    cout << maxSum << endl;
    return time_use;
}

void RandomArray(int a[], int n) {
    srand(time(NULL));
    for (int i = 0;i<n;i++)
        a[i] = rand() % 100000;

}
int main()
{
    double time_use = 0;
    int n;
    cout << "nhap so luong phan tu ban muon \n";
    cin >> n;
    int a[100000];
    RandomArray(a, n);
    cout << "Thoi gian thuc hien thuat toan 1 la:\n";
    if (ThuatToan1(a, n, time_use) == -1)
    {
        cout << "Qua 30s\n";
    }
    else
        cout << ThuatToan1(a, n, time_use) << "giay\n";
    cout << "Thoi gian thuc hien thuat toan 2 la:\n";
    if (ThuatToan2(a, n, time_use) == -1)
    {
        cout << "Qua 30s\n";
    }
    else
        cout << ThuatToan2(a, n, time_use) << "giay\n";
}