Сегодня мой 45-й день кодинга. Сегодня решил один вопрос.
Проблема: алгоритм Кадане
Дан массив Arr[] из N целых чисел. Найдите непрерывный подмассив (содержащий хотя бы одно число), который имеет максимальную сумму, и верните его сумму.
Пример 1:
Input: N = 5 Arr[] = {1,2,3,-2,5} Output: 9 Explanation: Max subarray sum is 9 of elements (1, 2, 3, -2, 5) which is a contiguous subarray.
Пример 2:
Input: N = 4 Arr[] = {-1,-2,-3,-4} Output: -1 Explanation: Max subarray sum is -1 of element (-1)
Ваша задача
Вам не нужно ничего читать или печатать. Задача состоит в том, чтобы завершить функцию maxSubarraySum(), которая принимает Arr[] и N в качестве входных параметров и возвращает сумму подмассива с максимальной суммой.
Ожидаемая временная сложность:O(N)
Ожидаемое вспомогательное пространство:O(1)
Решение (в Java):
class Solution{ // arr: input array // n: size of array //Function to find the sum of contiguous subarray with maximum sum. long maxSubarraySum(int arr[], int n){ // Your code here int msf=arr[0], meh=0; for( int i=0; i<n; i++){ meh=meh+arr[i]; if(meh<arr[i]) meh=arr[i]; if(msf<meh) msf=meh; } return msf; } }