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. # Given array arr[]
  38. def printArray(nums, startIndex, endIndex):
  39.     for i in range(startIndex, endIndex + 1):
  40.         print(nums[i], end = " ")
  41.  
  42. nums = [-86, 43, -45, 68, -21]
  43. maxSum, maxStart, maxEnd = SubarrayWithMaxSum(nums)
  44. invSum, invStart, invEnd = SubarrayWithMaxSum([-num for num in nums])
  45. if (maxSum > invSum):
  46.     printArray(nums, maxStart, maxEnd)
  47. else:
  48.     printArray(nums, invStart, invEnd)
Success #stdin #stdout 0.03s 9228KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-86 43 -45
https://ideone.com/PVRGyt
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!