Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

Example:

Input: [– 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6. Advanced:

If you already have an O(n) solution, try a more sophisticated divide-and-conquer solution.

The largest subarray of products blog.csdn.net/qq_42604176… Size = 0, nums.size = 0, nums.size = 0, nums.size = 0, nums.size = 0 [– 2, 1, 3, 4, 1, 2, 1, 5, 4] f: [-2,1, 1,4, 3,5,6,6, 6] for each number in the nums array, there are two options, one is to include it in f, and one is not to include it in f (and then start recording again from nums[I]) state transition equation: F [I] = Max (f[I]+nums[I],nums[I])

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
            int n=nums.size(),ans=nums[0];
            vector<int> f(n, 0);
            f[0]=nums[0];
			for(int i=1; i<n; ++i) { f[i] =max(nums[i],nums[i]+f[i- 1]);
				ans = max(ans,f[i]);		// Find the maximum values in each interval of different lengths and take the maximum of these values
			}
			returnans; }};Copy the code

The reason for the first error is that f[0] was not assigned an initial value.



But feel time and space consumption are relatively big, let me think is why…

Is there a big guy who can explain the optimization idea, or I will write optimization (DOGE) when I return after learning.