问题描述

The array usually contains both positive and negative numbers along with 0. For example, for the array of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

Some properties of this problem are:

1. If the array contains all non-positive numbers, then the solution is the number in the array with the smallest magnitude.
2. If the array contains all non-negative numbers, then the problem is trivial and the maximum sum is the sum of all the elements in the list.
3. An empty set is not valid.
4. There can be multiple different sub-arrays that achieve the same maximum sum to the problem.

//
// Created by krislyy on 2018/11/5.
//
// For example, for the
// sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray
// with the largest sum is 4, −1, 2, 1, with sum 6.
//

#ifndef ALGORITHM_MAXSUBARRAY_H
#define ALGORITHM_MAXSUBARRAY_H


namespace Algorithm {
    /*计算最大子数组，并返回范围*/
    static int max_subarray(int arr[], int len, int *begin, int *end){
        int subvalue = arr[0];
        int maxvalue = arr[0];
        *begin = 0;
        *end = 0;
        int newBegin = 0;

        for (int i = 1; i < len; ++i) {
            if(subvalue > 0) {    //正数继续操作接下来的元素
                subvalue += arr[i];
            } else {
                subvalue = arr[i]; //负数舍弃，继续
                newBegin = i;
            }

            if(maxvalue < subvalue) {
                maxvalue = subvalue;
                *begin = newBegin;
                *end = i;
            }
        }
        return maxvalue;
    }
};


#endif //ALGORITHM_MAXSUBARRAY_H

###Result###
array[-2,1,-3,4,-1,2,1,-5,4,]
max subarry is: 3 To 6
max subarry sum value is  6