//
you're reading...
00 - Chủ đề chung, Đề huấn luyện bằng tiếng Anh

English problems: Maximum subarray sum

Given an array of unordered positive and negative integers, find the maximum subarray sum in the array.
For example:
Array: {2, -9, 5, 1, -4, 6, 0, -7, 8}
Output:
Maximum subarray sum is 9.


Algorithm/Insights


1. Start with curSum = 0 and maxSum = 0.
2. Traverse the array elements, from i = 0 to n-1, where n is the length of the array.
a. Keep adding array elements to curSum till curSum >= 0 and update maxSum to curSum if maxSum < curSum.
b. As soon as curSum becomes < 0, reset curSum = 0.
3. Finally return maxSum.
This is known as Kadane’s algorithm.

The above method does not take care of the case when all the elements in the array are negative.
In this case, we can modify the algorithm, to keep a flag hasAllNegativeNumbers initialized to true.
If a positive or 0 element is seen in the array, then set hasAllNegativeNumbers = false.
Also, while traversing the array, keep track of maximum negative element.
Finally, if hasAllNegativeNumbers is true, then return maxNegativeSum, else return maxSum.

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Danh mục

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Palouse Falls at Sunrise (Palouse, WA)

Dartford Warbler

Herbal face

More Photos

Thống kê

  • 137,116 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: