kadaneのアルゴリズム
LeetCodeの問題を紹介します.
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.
アルゴリズム1:暴力列挙法,アルゴリズム複雑度O(N三次方)
アルゴリズムの2:アルゴリズムの1の改善、1つのfor循環を減らして、複雑度はO(N平方)です
int maxsequence2(int A[], int N) { int ThisSum, MaxSum = 0; int i, j; for (i = 0; i <= N; i++) { ThisSum = 0; for (j = i; j <= N; j++) { ThisSum += A[j]; if (ThisSum > MaxSum) MaxSum = ThisSum; } } return MaxSum; }
アルゴリズム3:分けて治す.アルゴリズム複雑度O(Nlogn)
int Max(int A, int B, int C) { /return A > B ? A > C ? A :C: B > C ? B : C;/ if (A > B) { if (A > C) return A; else return C; } else if (B > C) return B; else return C;
}int DivideAndConquer(int List[],int left,int right){int MaxLeftSum,MaxRightSum;int MaxLeftBoardSum,MaxRightBoardSum;int LeftBoardSum,RightBoardSum;int center,i;/再帰終了条件/if(left==right){if(List[left]>0)return List[left];else return 0;}
} int maxsequence3(int A[], int N) { return DivideAndConquer(A, 0, N-1); }
アルゴリズム四:オンライン処理アルゴリズム、コードが最も簡単で、複雑度が最も低く、O(N)である.
int maxsequence4(int A[], int N) { int ThisSum,MaxSum ; int i; ThisSum = MaxSum = 0; for (i = 0; i <= N; i++) { ThisSum += A[i]; if (ThisSum > MaxSum) MaxSum = ThisSum; else if (ThisSum < 0) ThisSum = 0; } return MaxSum;
}
主な手順は以下の通りです.
include
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.
アルゴリズム1:暴力列挙法,アルゴリズム複雑度O(N三次方)
int maxsequence1(int A[], int N)
{
int ThisSum , MaxSum=0;
int i, j, k;
for (i = 0; i <= N; i++) {
for (j = i; j <= N; j++) {
ThisSum = 0;
for (k = i; k <= j; k++)
ThisSum += A[k];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}アルゴリズムの2:アルゴリズムの1の改善、1つのfor循環を減らして、複雑度はO(N平方)です
int maxsequence2(int A[], int N) { int ThisSum, MaxSum = 0; int i, j; for (i = 0; i <= N; i++) { ThisSum = 0; for (j = i; j <= N; j++) { ThisSum += A[j]; if (ThisSum > MaxSum) MaxSum = ThisSum; } } return MaxSum; }
アルゴリズム3:分けて治す.アルゴリズム複雑度O(Nlogn)
int Max(int A, int B, int C) { /return A > B ? A > C ? A :C: B > C ? B : C;/ if (A > B) { if (A > C) return A; else return C; } else if (B > C) return B; else return C;
}int DivideAndConquer(int List[],int left,int right){int MaxLeftSum,MaxRightSum;int MaxLeftBoardSum,MaxRightBoardSum;int LeftBoardSum,RightBoardSum;int center,i;/再帰終了条件/if(left==right){if(List[left]>0)return List[left];else return 0;}
center = (right + left) / 2;
MaxLeftSum = DivideAndConquer(List, left, center);
MaxRightSum= DivideAndConquer(List, center+1, right);
MaxLeftBoardSum = 0; LeftBoardSum = 0;
for (i = center;i >= left; i--)
LeftBoardSum += List[i];
if (LeftBoardSum > MaxLeftBoardSum)
MaxLeftBoardSum = LeftBoardSum;
MaxRightBoardSum = 0; RightBoardSum = 0;
for (i = center + 1; i <= right; i++)
RightBoardSum += List[i];
if (RightBoardSum > MaxRightBoardSum)
MaxRightBoardSum = RightBoardSum;
return Max(MaxLeftSum, MaxRightSum, MaxRightBoardSum + MaxLeftBoardSum);
} int maxsequence3(int A[], int N) { return DivideAndConquer(A, 0, N-1); }
アルゴリズム四:オンライン処理アルゴリズム、コードが最も簡単で、複雑度が最も低く、O(N)である.
int maxsequence4(int A[], int N) { int ThisSum,MaxSum ; int i; ThisSum = MaxSum = 0; for (i = 0; i <= N; i++) { ThisSum += A[i]; if (ThisSum > MaxSum) MaxSum = ThisSum; else if (ThisSum < 0) ThisSum = 0; } return MaxSum;
}
主な手順は以下の通りです.
include