Tìm tổng lớn nhất của các dãy con liên tục

[Tuan_Cris (tạch C++)]

Viết chương trình hiệu quả để tìm tổng các phân đoạn liên tiếp trong một dãy số một chiều có tổng lớn nhất.

Em code bài này trên dev C++ thì chạy đúng yêu cầu nhưng khi sub lên spoj lại báo sai,các a sửa lại cho code nó tối ưu e với ạ.

#include<bits/stdc++.h>
using namespace std;
int maxSubArraySum(int a[], int n) 
{ 
   int max_so_far = a[0]; 
   int curr_max = a[0]; 
   for (int i = 1; i < n; i++) 
   { 
        curr_max = max(a[i], curr_max+a[i]); 
        max_so_far = max(max_so_far, curr_max); 
   } 
   return max_so_far; 
} 
int main() 
{ 
    int n,T;
    cin >> T;
    while(T--)
    {
    	cin >> n;
    	int a[n+1];
    	for(int i = 0; i < n; i++)
    		cin >> a[i];
		cout << maxSubArraySum(a,n) << endl;
	}
    return 0; 
}

[Sherly1001]

cout << maxSubArraySum(a,n);

Thêm endline vô.

[Tuan_Cris (tạch C++)]

mk thêm rồi mà vẫn ko đc bạn ạ

[Van_Nam2 (Nam Do)]

Mình không code C++ nhưng mình có JavaScript solution, bạn thử chuyển nó sang C++ xem sao:

var maxSubArray = function(nums) {
    let max = -Infinity; 
    let max_end = -Infinity;  
    for(let i = 0; i < nums.length; i++){ 
        max_end = max_end + nums[i]; 
        if(max_end < 0){
            max_end = 0;
        }else if(max < max_end){
            max = max_end
        }
    }
    return max
}

[noname00 (HK boy)]

Tổng 10^6 số có trị tuyệt đối 10^6 đạt max là 10^6 * 10^6 = 10^12, để int là bị tràn số rồi

cin >> n; int a[n+1];

C++ không có kiểu này.