最大サブ配列問題の3つの方法:分治法、暴力法、非再帰法
アルゴリズムの導論とその練習問題を参考にして、直接コードに行きます
// P38_MaxSubArray.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
using namespace std;
int main()
{
//
int calculateMaxSubArray(int arr[], int start, int end);
int calculateMaxSubArrayCrossMid(int arr[], int start, int mid, int end);
//
int calculateMaxSubArray_BaoLi(int arr[], int start, int end);
//
int calculateMaxSubArray_NoDiGui(int arr[], int start, int end);
int arr[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
// int arr[] = { -3, -2, -1, -2, -4, -5, -6, -7, -8, -89, -10, -11, -12, -13 };
int n = sizeof(arr) / sizeof(int);
cout << n << endl;
int max = calculateMaxSubArray(arr, 0, n);
cout << " " << max << endl;
max = calculateMaxSubArray_BaoLi(arr, 0, n);
cout << " " << max << endl;
max = calculateMaxSubArray_NoDiGui(arr, 0, n);
cout << " " << max << endl;
return 0;
}
int calculateMaxSubArrayCrossMid(int arr[], int start, int mid, int end) {
int left_sum = -10000, right_sum = -10000;
int sum = 0;
for (int i = mid - 1; i >= 0; i--) {
sum += arr[i];
if (left_sum < sum) {
left_sum = sum;
}
}
sum = 0;
for (int i = mid; i < end; i++) {
sum += arr[i];
if (right_sum < sum) {
right_sum = sum;
}
}
return left_sum + right_sum;
}
int calculateMaxSubArray(int arr[], int start, int end) {
if (start + 1 == end) {
return arr[start];
}
int mid = (start + end) / 2;
int m1 = calculateMaxSubArray(arr, start, mid);
int m2 = calculateMaxSubArray(arr, mid, end);
int m3 = calculateMaxSubArrayCrossMid(arr, start, mid, end);
m2 = m2 > m1 ? m2 : m1;
return m3 > m2 ? m3 : m2;
}
int calculateMaxSubArray_BaoLi(int arr[], int start, int end) {
int max = -10000;
int sum = 0;
for (int i = start; i < end; i++) {
for (int j = i; j < end; j++) {
sum = 0;
for(int k = i; k <= j; k++){
sum += arr[k];
}
if (sum > max) {
max = sum;
}
}
}
return max;
}
int calculateMaxSubArray_NoDiGui(int arr[], int start, int end) {
int s = start, e = 0, max = arr[0], sum = 0, right_sum = 0, sTmp = 0, eTmp = 0;
for (int i = start + 1; i < end; i++) {
right_sum = -10000;
sum = 0;
for (int j = i; j >= s; j--) {
sum += arr[j];
if (sum > right_sum) {
right_sum = sum;
sTmp = j;
}
}
eTmp = i;
if (right_sum > max) {
max = right_sum;
s = sTmp;
e = eTmp;
}
}
cout << s << ", " << e << endl;
return max;
}