fork download
copy 
  1. def SubarrayWithMaxSum(nums):
  2.  
  3.     # Initialize currMax and globalMax
  4.     # with first value of nums
  5.     currMax = nums[0]
  6.     globalMax = nums[0]
  7.  
  8.     # Iterate for all the elements
  9.     # of the array
  10.     for i in range(1, len(nums)):
  11.  
  12.         # Update currMax
  13.         currMax = max(nums[i], nums[i] + currMax)
  14.  
  15.         # Check if currMax is greater
  16.         # than globalMax
  17.         if (currMax > globalMax):
  18.             globalMax = currMax
  19.             endIndex = i
  20.  
  21.     startIndex = endIndex
  22.  
  23.     curGlobalMax = globalMax
  24.     # Traverse in left direction to
  25.     # find start Index of subarray
  26.     while (startIndex >= 0):
  27.         curGlobalMax -= nums[startIndex]
  28.  
  29.         if (curGlobalMax == 0):
  30.             break
  31.  
  32.         # Decrement the start index
  33.         startIndex -= 1
  34.  
  35.     return globalMax, startIndex, endIndex
  36.  
  37. def SubarrayWithMinSum(nums):
  38.  
  39.     # Initialize currMin and globalMin
  40.     # with first value of nums
  41.     currMin = nums[0]
  42.     globalMin = nums[0]
  43.  
  44.     # Iterate for all the elements
  45.     # of the array
  46.     for i in range(1, len(nums)):
  47.  
  48.         # Update currMin
  49.         currMin = min(nums[i], nums[i] + currMin)
  50.  
  51.         # Check if currMin is greater
  52.         # than globalMin
  53.         if (currMin < globalMin):
  54.             globalMin = currMin
  55.             endIndex = i
  56.  
  57.     startIndex = endIndex
  58.  
  59.     currGlobalMin = globalMin
  60.     # Traverse in left direction to
  61.     # find start Index of subarray
  62.     while (startIndex >= 0):
  63.         currGlobalMin -= nums[startIndex]
  64.  
  65.         if (currGlobalMin == 0):
  66.             break
  67.  
  68.         # Decrement the start index
  69.         startIndex -= 1
  70.  
  71.     return globalMin, startIndex, endIndex
  72.  
  73. # Given array arr[]
  74. def printArray(nums, startIndex, endIndex):
  75.     for i in range(startIndex, endIndex + 1):
  76.         print(nums[i], end = " ")
  77.  
  78. nums = [-86, 43, -45, 68, -21]
  79. maxSum, maxStart, maxEnd = SubarrayWithMaxSum(nums)
  80. minSum, minStart, minEnd = SubarrayWithMinSum(nums)
  81. if (maxSum > abs(minSum)):
  82.     printArray(nums, maxStart, maxEnd)
  83. else:
  84.     printArray(nums, minStart, minEnd)
  85.  
Success #stdin #stdout 0.02s 9156KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-86 43 -45
https://ideone.com/nm3qZW
language:
Python 3 (python  3.12)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!