算法导论第四章-第一节：暴力求解最大子数组问题

暴力求解没什么好多说的，复杂度为O(n^2).

直接贴代码话说c语言的数组处理确实麻烦。。

//暴力求解最大子数组的问题
#include <stdio.h>
#include <stdlib.h>

int *bruteForce(int arr[], int len);

int main()
{
    int arr[16] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
    int *result = bruteForce(arr, 16);
    printf("左边界为%d", result[0]);
    printf("右边界为%d", result[1]);
    printf("最大子数组的和为%d", result[2]);
    free(result);
    return 0;
}
//返回最大自数组的左右边界和最大子数组的和
int *bruteForce(int arr[], int len)
{
    int *a;
    a = calloc(3, sizeof(int));
    int sum = arr[0];
    int leftIndex = 0;
    int rightIndex = 0;
    for (int i = 0; i < len; i++)
    {
        int curSum = 0;
        for (int j = i; j < len; j++)
        {
            curSum += arr[j];
            if (curSum > sum)
            {
                sum = curSum;
                leftIndex = i;
                rightIndex = j;
            }
        }
    }
    a[0] = leftIndex;
    a[1] = rightIndex;
    a[2] = sum;
    return a;
}

PS:最近公司比较忙。。。。人每天晕乎乎的，也没什么时间看书。下周调整调整，多留点时间研究算法了。每周完成一章是底线。