Bernard Wong
  • Software Engineer
  • Problems
    • Lowest Common Ancestor of a Binary Tree
    • Longest Substring Without Repeating Characters
    • Longest Palindromic Substring
    • Longest Common Prefix
    • Isomorphic Strings
    • Integer to Roman
    • Frog Jump
    • Find the Difference
    • Find k closest elements to a given value
    • Longest Common Subsequence
    • Binary Search Tree from Sorted Array
    • Balanced Binary Tree
    • Sort Using Two Stacks
    • O(1) Stack
    • k-th element to last of a LinkedList
    • Dedup LinkedList
    • Check Rotated String
    • Compress String by Character Count
    • Escape HTML whitespace
    • Check String Permutation
    • Unique String
    • Container With Most Water
    • 4 Sum
    • 3 Sum Closest
    • 3 Sum
    • 2 Sum
    • Maximum Subarray
    • Nested List Weight Sum
    • Palindrome Number
    • Pow(x, n)
    • Regular Expression Matching
    • Remove Nth Node From End of List
    • Reverse Integer
    • Roman to Integer
    • Rotate Array
    • Search a 2D Matrix
    • Shortest Word Distance
    • Two Sum III - Data structure design
    • Valid Parentheses
    • ZigZag Conversion
    • Quicksort
    • Add Two Numbers
    • Best Time to Buy and Sell Stock
    • Letter Combinations of a Phone Number
  • Data Structures
    • Heap
Powered by GitBook
On this page
  1. Problems

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array

[-2,1,-3,4,-1,2,1,-5,4],

the contiguous subarray

[4,-1,2,1]

has the largest sum = 6.

def maxSubArray(nums: Array[Int]): Int = {
  var sum = nums.head
  var maxSum = nums.head
  for (i <- nums) {
    sum = i max sum + i
    maxSum = sum max maxSum
  }
  maxSum
}

val nums = Array(-2, 1, -3, 4, -1, 2, 1, -5, 4)
maxSubArray(nums)

Previous2 SumNextNested List Weight Sum

Last updated 6 years ago