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.

 to see which companies asked this question.

求出最大子数组之和

1. public class Solution {
2. public int MaxSubArray(int[] nums) {
3. if (nums.Length == 0)
4. {
5. return 0;
6. }
7. int max = nums[0],sum = 0;
8. for (int i = 0; i < nums.Length; i++)
9. {
10. if (sum < 0)
11. {
12. sum = nums[i];
13. }
14. else
15. {
16. sum += nums[i];
17. }
18. if (sum > max)
19. {
20. max = sum;
21. }
22. }
23. return max;
24. }
25. }