专栏首页Euclid学习日记最大子序列和(leetcode)
原创

最大子序列和(leetcode)

1.暴力求解(超时)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int sum;
        for(int i = 0;i < nums.size();i++){
            for(int j = i;j < nums.size();j++){
                sum = 0;//计算nums[i]到nums[j]
                for(int k = i;k <= j;k++){
                    sum = sum + nums[k];
                    if(maxSum < sum) maxSum = sum;
                }
            }
        }
        return maxSum;
    }
};

2.暴力求解进化版:重复计算nums[i]到nums[j-1]的值

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int sum;
        for(int i = 0;i < nums.size();i++){
            sum = 0;
            for(int j = i;j < nums.size();j++){
                    sum = sum + nums[j];
                    if(maxSum < sum) maxSum = sum;
                }
            }
        return maxSum;
    }
};

3.贪心算法

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int arrSum = nums[0];
        for(int i = 1;i < nums.size();i++){
            arrSum = max(nums[i],arrSum + nums[i]);
            maxSum = max(maxSum, arrSum);
        }
        return maxSum;
    }
};

4.分治法

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int right = nums.size()-1;
        int left = 0;
        int result = maxSubArrayHelp(nums, left, right);
        return result;
    }
    int maxSubArrayHelp(vector<int>& nums,int left,int right){
        //递归中止条件
        if(left == right) return nums[left];

        //递归
        int mid = (left + right)/2;
        int leftsum = maxSubArrayHelp(nums, left, mid);
        int rightsum = maxSubArrayHelp(nums, mid+1, right);
        int midsum = maxSubArrayMid(nums, left, right, mid);

        //判断三者中的最大值
        int result = max(leftsum, rightsum);
        int z = max(result, midsum);

        return z;
    }

    int maxSubArrayMid(vector<int>& nums,int left, int right,int mid){
        int leftSum = INT_MIN;
        int sum = 0;

        //从mid开始向左的序列的最大值
        for(int i = mid;i >= left;i--){
            sum = sum + nums[i];
            leftSum = max(sum, leftSum);
        } 
        int rightSum = INT_MIN;
        sum = 0;
        //从mid向右的最大值
        for(int j = mid+1;j <= right;j++){
            sum = sum + nums[j];
            rightSum = max(sum, rightSum);
        }

        return rightSum + leftSum;
    }
};

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 杨辉三角 II(leetcode.119)

    Cnk​=n!/(k!(n−k)!)=(n∗(n−1)∗(n−2)∗...(n−k+1))/k!

    euclid
  • 合并两个有序数组(leetcode.88)

    euclid
  • 寒假学习计划

    今年考研感觉不太好,借助寒假系统的复习一遍java web和大学其他知识(还有高数/(ㄒoㄒ)/~~)

    euclid
  • LeetCode 494. 目标和(DFS+DP)

    给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符...

    Michael阿明
  • LeetCode268. 缺失数字

    mathor
  • 【Code】关关的刷题日记22——Leetcode 53. Maximum Subarray

    关小刷刷题 22——Leetcode 53. Maximum Subarray 题目 Find the contiguous subarray within a...

    WZEARW
  • Leetcode 1365. 有多少小于当前数字的数字(C语言)

    给你一个数组 nums,对于其中每个元素 nums[i],请你统计数组中比它小的所有数字的数目。

    Kindear
  • LeetCode 666. 路径和 IV(树的遍历)

    给定一个包含三位整数的升序数组,表示一棵深度小于 5 的二叉树, 请你返回从根到所有叶子结点的路径之和。

    Michael阿明
  • 小白刷力扣之两数之和

    作为一个半路出家的算法小白,最近尝试着刷一下力扣,来扩展些思维,毕竟总是写一些复杂度非常高的代码也不是那么回事。

    周萝卜
  • Leetcode 268. Missing Number

    Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find ...

    triplebee

扫码关注云+社区

领取腾讯云代金券