// 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;
    start = clock();
    for (int i = 0; i < n; i++)
    {
        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();

    time_use = (double)(end - start) / CLOCKS_PER_SEC;
    return time_use;
}

double ThuatToan2(int a[],int n,double &time_use)
{
    int maxSum = 0, thisSum = 0;
    clock_t start, end;
    start = clock();
    for (int j = 0; j < n; j++)
    {
        thisSum += a[j];
        if (thisSum > maxSum)
            maxSum = thisSum;
        else if (thisSum < 0)
            thisSum = 0;
    }
    end = clock();
    time_use = (double)(end - start) / CLOCKS_PER_SEC;
    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";
    cout << ThuatToan1(a, n, time_use) << "giay\n";
    cout << "Thoi gian thuc hien thuat toan 2 la:\n";
    cout << ThuatToan2(a, n, time_use) << "giay\n";
}