C语言刷题 LeetCode 30天挑战 （三）动态规划、分治法

//Maximum Subarray
//Given an integer array nums , find the contiguous subarray 
//(containing at least one number) which has the largest sum and return itssum.
//Example:
//input:[-2,1,-3,4,-1,2,1,-5,4],
//output:6
//Explanation:[4,-1,2,1]has the largest sum = 6.
//Follow up:
//If you have figured out the O(n) solution, 
//try coding another solution using the divide and conquer approach,
//which is more subtle.

#include <stdio.h>
#include <limits.h>

//动态规划（Kadane's算法）
int maxSubArray1(int *nums,int numsSize){
    int current_sum = nums[0];
    int max_sum = nums[0];
    
    for (int i = 1; i < numsSize; ++i) {
        // Update the current_sum: either continue with current subarray or start new
        current_sum = (current_sum + nums[i] > nums[i]) ? 
                        current_sum + nums[i] : nums[i];
        // Update the max_sum if current_sum is greater
        max_sum = (current_sum > max_sum) ? current_sum : max_sum;
    }
    return max_sum;
}

//分治法
// Function to find the maximum crossing subarray sum
//利用递归将数组分成两部分，分别计算左、右子数组和跨越中点的子数组的最大和。
int maxCrossingSubArray(int* nums, int left, int mid, int right) {
    int left_sum = INT_MIN;
    int total = 0;
    for (int i = mid; i >= left; i--) {
        total += nums[i];
        if (total > left_sum) {
            left_sum = total;
        }
    }
    
    int right_sum = INT_MIN;
    total = 0;
    for (int i = mid + 1; i <= right; i++) {
        total += nums[i];
        if (total > right_sum) {
            right_sum = total;
        }
    }
    
    return left_sum + right_sum;
}

// Helper function to find maximum subarray sum using divide and conquer
int maxSubArrayHelper(int* nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }
    
    int mid = (left + right) / 2;
    int left_max = maxSubArrayHelper(nums, left, mid);
    int right_max = maxSubArrayHelper(nums, mid + 1, right);
    int cross_max = maxCrossingSubArray(nums, left, mid, right);
    
    if (left_max >= right_max && left_max >= cross_max) {
        return left_max;
    } else if (right_max >= left_max && right_max >= cross_max) {
        return right_max;
    } else {
        return cross_max;
    }
}

// Main function to find the maximum subarray sum
int maxSubArray2(int* nums, int numsSize) {
    return maxSubArrayHelper(nums, 0, numsSize - 1);
}

int main()
{
    int nums[] = {-2,1,-3,4,-1,2,1,-5,4};
    int count1 = maxSubArray1(nums,sizeof(nums)/sizeof(nums[0]));
    int count2 = maxSubArray2(nums,sizeof(nums)/sizeof(nums[0]));
    printf("%d\n",count1);
    printf("%d\n",count2);
    return 0;
}

原文地址：https://blog.csdn.net/weixin_64593595/article/details/142578543

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！