1【算法】——最大子数组问题（maximum subarray）

本文主要是介绍1【算法】——最大子数组问题（maximum subarray），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一.问题描述

        假如我们有一个数组，数组中的元素有正数和负数，如何在数组中找到一段连续的子数组，使得子数组各个元素之和最大。

二.问题分析

分治法求解：

初始状态：

low=0；high=A.length-1；mid=（low+high）/2；

求解A的最大子数组，A[i,j]，有以下三种情况：

1. 完全位于A[low,mid]
2. 完全位于A[mid+1,high]
3. 跨越中点

1与2仍为最大子数组问题，只是规模更小

对于3，任何跨越中点的子数组都由两个子数组组成A[i,mid],A[mid+1,j]

只需要找到A[low,mid]和A[mid+1,high]的最大子数组，然后进行合并即可。

代码实现：

#include<iostream>using namespace std;int find_max_crossing_subarray(int arr[],int low,int high){if(high==low){return arr[low];}int mid=(low+high)/2;int left=-1,right=-1,i,sum=0,max_left,max_right;for(i=mid;i>=low;i--){sum+=arr[i];if(sum>left){left=sum;max_left=i;}}sum=0;for(i=mid+1;i<=high;i++){sum+=arr[i];if(sum>right){right=sum;max_right=i;}}return left+right;
}
int max(int a,int b,int c){if(a>=b&&a>=c){return a;}else if(b>=a&&b>=c){return b;}else{return c;}
}
int find_max_subarray(int arr[],int low,int high){if(high==low){return arr[low];}int mid=(low+high)/2;int left=find_max_subarray(arr, low, mid);int right=find_max_subarray(arr, mid+1, high);int m=find_max_crossing_subarray(arr, low, high);return max(left,right,m);
}int main(){int arr[] = {5, 4, -17, 7, 8};cout<<find_max_subarray(arr, 0, 4);return 0;
}

动态规划求解：

对于一个有n个元素的数组arr[n]：

记maxSum（n）为该数组前n个元素和的最大值

p（n）为前n个元素中以第n元素结尾的最大子数组和

则有：

int find_max_subarray_dp(int arr[],int low,int high){if(high==low){return arr[low];}int p[100],maxsum[100];p[0]=arr[0];maxsum[0]=arr[0];for(int i=1;i<=high;i++){if(arr[i]>(arr[i]+p[i-1])){p[i]=arr[i];}else{p[i]=arr[i]+p[i-1];}}for(int i=1;i<=high;i++){if(p[i]>maxsum[i-1]){maxsum[i]=p[i];}else{maxsum[i]=maxsum[i-1];}}return maxsum[high];
}

这篇关于1【算法】——最大子数组问题（maximum subarray）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---