"""
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
"""
"""
author:jiyanjiao
date :2019-10-21
"""


class Solution:
    max_index = 0   # 子数组和最大的索引
    max_sum = 0     # 子数组和的最大值
    sum_list = []   # 子数组和的列表
    sub_list = []   # 最大和的子数组列表

    def maxSubArray(self, nums_list, le) -> int:
        """
        :param nums_list: 传入的数组
        :param le: 期望的子数组的长度
        :return: 子数组和最大值,最大和的子数组的列表
        """
        if le > len(nums_list):
            raise Exception('子数组长度大于父数组长度')
        elif le < 1 or len(nums_list) == 0:
            raise Exception("父数组不能为空,或者,子数组至少包含一个元素")
        elif le == len(nums_list):
            raise Exception("仅有一组数不符合规则")

        # 求指定长度子数组的和
        for i in range(len(nums_list)-1):
            s_sum = 0
            for j in range(i, i+le):
                # 子数组顺序的组合情况,去掉最后一组不够长度的子数组
                if len(nums_list) % le == 0:
                    s_sum += nums_list[j]
                else:
                    s_sum += nums_list[j-1]
                i += 1
            self.sum_list.append(s_sum)

        # 求子数组和的最大值,和最大值索引
        for i in range(len(self.sum_list)-1):
            for j in range(i+1, len(self.sum_list)):
                if len(nums_list) % le == 0:
                    if self.sum_list[i] > self.sum_list[j]:
                        self.max_sum = self.sum_list[i]
                        self.max_index = i
                    else:
                        self.max_sum = self.sum_list[j]
                        self.max_index = j
                else:
                    if self.sum_list[i] > self.sum_list[j]:
                        self.max_sum = self.sum_list[i]
                        self.max_index = i
                    else:
                        self.max_sum = self.sum_list[j]
                        self.max_index = j-1

        # 根据子数组和的最大值索引算出子数组在符数组中索引
        for i in range(self.max_index-1, self.max_index+le):
            self.sub_list.append(nums_list[i])

        print("传入的数组是{},{}个长度的连续子数组最大和为{},最大和的数组为{}".format(nums_list, le, self.max_sum, self.sub_list))

    # 求数组中的值的和 本次未用到
    def sumArray(self, num_list):
        sum = 0
        for i in range(len(num_list)):
            sum += num_list[i]
        return sum


# Your MedianFinder object will be instantiated and called as such:
if __name__ == '__main__':
    pass

    # obj = MedianFinder()
    # obj.addNum(1)
    # obj.addNum(2)
    # obj.addNum(4)
    # obj.addNum(3)
    # obj.addNum(5)
    # param_2 = obj.findMedian()

    s = Solution()
    # s.maxSubArray([1,2,3,4,5,6])
    s.maxSubArray([-1,2,1,0,0],3)
    

注: 这是小编自行整理,仅仅是实现了功能,不设计算法,正确的解法如下:有待研究~~

  

01-16 13:02