Untitled

ll kadane_mat(ll** mat, long rows, long cols) {
    int left_index, right_index;
    ll* temp_arr, curr_sum;
    ll max_sum = LLONG_MIN;

    for (left_index = 0; left_index < cols; left_index++) {
        temp_arr = new ll[rows]();

        for (right_index = left_index; right_index < cols; right_index++) {

            for (int i = 0; i < rows; i++) {
                //creating to working array 
                //if left_index = right_index than the array will be the same as 
                //matrix column = left_index
                temp_arr[i] += mat[i][right_index];
            }
            //calculating curretn sub array max sum
            curr_sum = kadane_arr(temp_arr, rows);

            if (curr_sum > max_sum)
                max_sum = curr_sum;
        }
        delete[] temp_arr;
    }
    return max_sum;
}


ll kadane_arr(ll* arr, long size) {
    ll sum = 0, max_sum = LLONG_MIN;
    ll neg_sum = arr[0];    
    int i;

    for (i = 0; i < size; i++) {
        sum += arr[i];

        if (arr[i] > neg_sum && arr[i] < 0)
            neg_sum = arr[i];

        if (sum < 0)
            sum = 0;
        else if (sum > max_sum) {
            max_sum = sum;
        }
    }
    //if all numbers are negative, the func. return neg_sum
    //which is the highest negative number in the current array
    return max(neg_sum, max_sum);
}