Kadane의 알고리즘
2561 단어 javadatastructurealgorithms
N개의 정수 배열 Arr[]이 주어집니다. 합이 최대인 연속된 하위 배열(적어도 하나의 숫자 포함)을 찾아 그 합을 반환합니다.
예 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.
class Solution{
// arr: input array
// n: size of array
//Function to find the sum of contiguous subarray with maximum sum.
int maxSubarraySum(int arr[], int n){
int maxSoFar=0,maxTillHere=0;
for(int i=0;i<n;i++){
maxTillHere+=arr[i];
if(maxTillHere>maxSoFar){
maxSoFar=maxTillHere;
}
if(maxTillHere<0){
maxTillHere=0;
}
}
return maxSoFar;
}
}
Reference
이 문제에 관하여(Kadane의 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/prashantrmishra/kadanes-algorithm-2m34텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)