题目：最大子数组和

1.题目描述

所谓的最大子数组问题，指的是：给定一个数组A，寻找A的和最大的非空连续子数组。比如，数组 A = [-2, -3, 4, -1, -2, 1, 5, -3]， 最大子数组应为[4, -1, -2, 1, 5],其和为7。

2.解题思路

  2.1 动态规划

  2.2 分治法

3.代码

 3.1 动态规划

#include <iostream>

using namespace std;

void Max_subarray(int A[],int array_start,int array_end)
{
    int sum = 0;
    int Max = -999999;
    int high,low;
    int currentHigh,currentLow;
    for (int i = array_start;i <= array_end; i++)
    {   high = i;
        sum = sum + A[i];
        if (A[i] > sum)
          {
            sum = A[i];
            low = i;
          }
        if (sum > Max)
          {
            Max = sum;
            currentLow = low;
            currentHigh = high;
          }
    }
    cout << currentLow << " " << currentHigh << " " << Max << endl;
}
int main()
{
    int A[16] = {-13, -3, 25, 20, -3, -16, -23, 18, 110, -7, -12, -5, -22, 15, -4, 7};
    Max_subarray(A,5,15);
    return 0;
    return 0;
}

3.2 分治法

#include <iostream>

using namespace std;

typedef struct
{
    int subarray_start;
    int subarray_end;
    int subarray_max;

}result;

result Find_max_crossing_subarray(int A[],int array_start,int array_mid,int array_end)
{
    result cross_result;
    int left_sum = -999999;
    int right_sum = -999999;
    int max_left;
    int max_right;
    cout << array_start << " " << array_mid << ' ' << array_end << endl;
    int sum = 0;
    for (int i = array_mid; i >= array_start; i--)
      {
          sum = sum + A[i];
          if (sum > left_sum)
             {
                left_sum = sum;
                max_left = i;
             }
      }

    sum = 0;
    for (int i = array_mid + 1; i <= array_end; i++)
      {
          sum = sum + A[i];
          if (sum > right_sum)
             {
                right_sum = sum;
                max_right = i;
             }
      }

    cross_result.subarray_start = max_left;
    cross_result.subarray_end = max_right;
    cross_result.subarray_max = left_sum + right_sum;
    cout << max_left << ' ' << max_right << " " << left_sum + right_sum << endl;
    cout << "-----" << endl;
    return cross_result;
}

result Max_subarray(int A[],int array_start,int array_end)
{
    if (array_start == array_end)
    {
        result end_start;
        end_start.subarray_start = array_start;
        end_start.subarray_end = array_end;
        end_start.subarray_max = A[array_end];
        return end_start;
    }

    result left_result,right_result,cross_result;
    int mid = (array_start + array_end) / 2;

    left_result = Max_subarray(A,array_start,mid);
    right_result = Max_subarray(A,mid+1,array_end);
    cross_result = Find_max_crossing_subarray(A,array_start,mid,array_end);

    if (left_result.subarray_max >= right_result.subarray_max && left_result.subarray_max >= cross_result.subarray_max)
              return left_result;
    else if (right_result.subarray_max >= left_result.subarray_max && right_result.subarray_max >= cross_result.subarray_max)
              return right_result;
    else
              return cross_result;

}
int main()
{
    int A[16] = {-13, -3, 25, 20, -3, -16, -23, 18, 110, -7, -12, -5, -22, 15, -4, 7};
    result my_result;
    my_result = Max_subarray(A,0,15);
    cout << my_result.subarray_start << " " << my_result.subarray_end << " " << my_result.subarray_max;
    return 0;
}