题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
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.

解题

自己的方法

利用数据结构：无
利用算法：动态规划
复杂度O(n)

代码：

1
2
3
4
5
6
7
8
9
public int maxSubArray(int[] nums) {
        int max=nums[0];
        int temp=max;
        for(int i=1;i<nums.length;i++){
            temp=Math.max(nums[i]+temp,nums[i]);
            max=Math.max(temp, max);
        }
        return max;
    }

思路：
无非就是用一个值(temp)储存中间连续元素的和，在用另外一个值(max)表示到目前为止的最大值，首先比较temp加上后一个元素和那个元素不加temp谁大，如果不加temp说明nums[i]更大，便把它的值赋给temp，继续累加，期间不断更新max值；
这种记录中间产生变量，并在循环后加以运用的思想被称作动态规划

总结

动态规划在这里刚刚浮出水面，我将在后面做一些专门的补充，来说明动态规划的特点和做题时的应用场景