Untitled
unknown
plain_text
3 years ago
1.4 kB
6
Indexable
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); }
Editor is loading...